Maps, Hash Tables, and Skip Lists

Maps, Hash Tables, and Skip Lists

1. Hash Tables

   • The novel concept for a hash table is the use of a hash function to map general keys to corresponding indices in a table.
     • Ideally, keys will be well distributed in the range from 0 to N −1 by a hash function, but in practice there may be two or more distinct keys that get mapped to the same index.
       • As a result, we will conceptualize our table as a bucket array
   • Hash Function: to map each key k to an integer in the range [0,N − 1], where N is the capacity of the bucket array for a hash table.
   • AbstractHasMap
     • createTable()
     • bucketGet(h,k)
     • bucketPut()
     • bucketRemove(h,k)
     • entrySet()

Bilder und Dateien der Mindmap