–tags: Data Structures

Hash based data structures:

Associative arrays:

  • Employee id to get name of employees
  • Keys and values; Keys must be unique
  • Values dont have to be complex
  • Different names to same thing: hash, dictionanry, hashtable, hashmap
  • mostly implemented using hashtable on the behind

Hash functions:

  • Crypto to data structure
  • Taking the data through a function and pass it to hash function and make small data that represents.
  • Hashing is not encryption: not invertible (lose into the hash function from data)
  • hashes are trivial
  • two objects that are equal must return same hash
  • two different objects might return the same hash
  • Boil it down to hash is very much valuable in data structure

Hash Tables:

  • They are very fast to insert and add delete data
  • Get us pass the limitations of an array
  • Multiple placeholders: buckets: entries in a hash table
  • add key and value to hash function
  • the value produced by hash function is boiled down to the no of available buckets and stored
  • the key then can be passed to hash function to look up entries
  • hash collisions:
    • dealing the buckets as lists; after finding bucket simply iterate through the list till we
    • find something we are looking for
    • separate chaining: above process: two or three items in the bucket doesn’t create big problem

Supporting hashing:

  • Every class in Java has the hashcode() behaviour
  • Python has a hash function hash()
  • We already have the behavior
  • Hashing in custom classes
  • Comparing two objects to equate using check into internal state
  • If you redefine equality, redefine hashing so that hash produced is same for both
  • String objects already have a hash

Language support:

  • Dictionary type in Python does hashing
  • Hash in Ruby
  • Hashtable class in . NET
  • String dictionary class makes it hashtables of strings and also Dictionary in .NET
  • Java has Hashmap, Hashtable, ConcurrentHashMap