–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