HASHING:
*The problem at hands is to speed up searching. Consider the problem of searching an array for a given value.
*If the array is not sorted, the search might require examining each and all elements of the array.
*If the array is sorted, we can use the binary search, and therefore reduce the worse-case runtime complexity to O(log n).
*We could search even faster if we know in advance the index at which that value is located in the array.
*Suppose we do have that magic function that would tell us the index for a given value.
*With this magic function our search is reduced to just one probe, giving us a constant runtime O(1). Such a function is called a hash function .
*A hash function is a function which when given a key, generates an address in the table.
*A hash function that returns a unique hash number is called a universal hash function.
*In practice it is extremely hard to assign unique numbers to objects.
*The later is always possible only if you know (or approximate) the number of objects to be proccessed.
*Priority Queue:
- We are often faced with a situation in which certain events/elements in life have higher or lower priorities than others.
- For example, university course prerequisites, emergency vehicles have priority over regular vehicles.
- A Priority Queue is like a queue, except that each element is inserted according a given priority.
- The simplest example is provided by real numbers and ≤ or ≥ relations over them. We can say that the smallest (or the largest) numerical value has the highest priority.
- In practice, priority queues are more complex than that. A priority queue is a data structure containing records with numerical keys (priorities) that supports some of the following operations:
Construct a priority queue
- Insert a new item.
- Remove an item.with the highest priority
- Change the priority
- Merge two priority queues
HashMap
*HashMap is a collection class that is designed to store elements as key-value pairs.
*Maps provide a way of looking up one thing based on the value of another.
String[] data = new String("Nothing is as easy as it looks").split(" ");
HashMap‹String, Integer> hm = new HashMap‹String, Integer>();
for (String key : data)
{
Integer freq = hm.get(key);
if(freq == null) freq = 1; else freq ++;
hm.put(key, freq);
}
System.out.println(hm);
*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.
