Hash Table

External

• http://en.wikipedia.org/wiki/Hash_table

Internal

• Data Structures
• Associative Array
• Distributed Hash Table
• Java HashMap

Overview

Hash tables are one of the most used data structures in programming. They don't have that many operations (INSERT(), DELETE() and SEARCH()), but what they do, they do really well. Conceptually, a hash table is an array that provides immediate random access for constant time insertion, deletion and lookup based on an arbitrary key and not an integral index.

Canonical Use

• The 2-SUM Problem

Supported Operations

INSERT(X)

INSERT(X)

DELETE(K)

DELETE(X)

SEARCH(K)

SEARCH(K)

TO DEPLETE

HashTableTODEPLETE