Hash : How does it work internally?

by

  1. Here is a good explanation about hashing. For example you want to store the string “Rachel” you apply a hash function to that string to get a memory location. myHashFunction(key: "Rachel" value: "Rachel") --> 10. The function may return 10 for the input “Rachel” so assuming you have an array of size 100 you store “Rachel” at index 10. If you want to retrieve that element you just call GetmyHashFunction("Rachel") and it will return 10. Note that for this example the key is “Rachel” and the value is “Rachel” but you could use another value for that key for example birth date or an object. Your hash function may return the same memory location for two different inputs, in this case you will have a collision you if you are implementing your own hash table you have to take care of this maybe using a linked list or other techniques.

  2. Here are some common hash functions used. A good hash function satisfies that: each key is equally likely to hash to any of the n memory slots independently of where any other key has hashed to. One of the methods is called the division method. We map a key k into one of n slots by taking the remainder of k divided by n. h(k) = k mod n. For example if your array size is n = 100 and your key is an integer k = 15 then h(k) = 10.

  3. Hashtable is synchronised and Hashmap is not.
    Hashmap allows null values as key but Hashtable does not.

  4. The purpose of a hash table is to have O(c) constant time complexity in adding and getting the elements. In a linked list of size N if you want to get the last element you have to traverse all the list until you get it so the complexity is O(N). With a hash table if you want to retrieve an element you just pass the key and the hash function will return you the desired element. If the hash function is well implemented it will be in constant time O(c) This means you dont have to traverse all the elements stored in the hash table. You will get the element “instantly”.

  5. Of couse a programer/developer computer scientist needs to know about data structures and complexity =)

More Related Contents:

  1. Data Structure in Java
  2. Deciding a Big-O notation for an algorithm
  3. How to check if an integer is in a set of given ranges? [closed]
  4. Why does Java’s hashCode() in String use 31 as a multiplier?
  5. How to detect a loop in a linked list?
  6. Stack with find-min/find-max more efficient than O(n)?
  7. Anagram algorithm in java
  8. Sample Directed Graph and Topological Sort Code [closed]
  9. What hashing function does Java use to implement Hashtable class?
  10. How to restore the PriorityQueue to its initial state before the method call?
  11. How to determine if binary tree is balanced?
  12. How to implement a Median-heap
  13. The simplest algorithm for poker hand evaluation
  14. Finding the shortest path nodes with breadth first search
  15. NullPointerException in onPostExecute [duplicate]
  16. Stack algorithm is not working pefectly in Java
  17. Sort on a string that may contain a number
  18. Obtaining a powerset of a set in Java
  19. Why should I use Deque over Stack?
  20. How to hash a string in Android?
  21. Data structures that can map a range of keys to a value
  22. Implement Stack using Two Queues
  23. How to count possible combination for coin problem
  24. Is there an efficient algorithm for integer partitioning with restricted number of parts?
  25. sorting integers in order lowest to highest java
  26. How to create a HashMap with two keys (Key-Pair, Value)?
  27. Can SHA-1 algorithm be computed on a stream? With low memory footprint?
  28. How does the Euclidean Algorithm work?
  29. Java Smooth Color Transition
  30. Generate Subject Hash of X509Certificate in Java

Leave a Comment