Hash Tables

  • Perfect hash function: no collision

  • In C++, hash table is implemented by unordered_set or unordered_map.

  • An unordered_set is an implementation of the 'set' interface, that uses the hash table as the data structure.

  • In other words: unordered_set is an abstract data type implemented the set interface. This is implemented with a hash table data structure backend.

  • unordered_map is an map ADT implemented with a hash table data structure.

Resolving collisions

  • Double hashing:
    • h_1(x) : to determine the position to insert the key
    • h_2(x) : the offsets from that position
  • Random hashing: randomly generate offsets
  • prime number size of hash table: you're not gonna have problem with common factor with the key you are going to insert. e.g. even size, even number key, can't distribute well.
  • load factor = N/M , N= # of elements in the table, M = size of the table
  • REFERENCE: UCSD CSE100 Data Structure Podcast 01/27/2017 & 01/30/2017

results matching ""

    No results matching ""