Hash tables (or hash maps) are used to store element and check if they exist during the program.
Hash Tables are used in the following formats:
- Pure key-value: Used to remember the existence of something and retrieve its value.
- Frequency table: Used to record the frequency of elements, especially in arrays with duplicates.
- Aggregator: Used when multiple values exist for a given key.
- Dictionary to look for alphabet characters in a string: For dealing with "abc...z". An integer array of size 26 can be used.
There are various pattern associated with Hash tables such as:
- Canonical Forms: Used to convert data with multiple representations into a unique representation called its canonical form.
- Caches: Utilized for efficient lookup of items. Examples include LRU (Least Recently Used) cache.
- Hashtable with Doubly Linked List: Combining hash tables with doubly linked lists to achieve certain functionalities.
- Hashtable with Binary Search Trees: Combining hash tables with binary search trees for specific requirements.
- Subarray Sums: Patterns involving calculating sums of subarrays.
- Searching for Specific Item in a Matrix: Techniques for finding a specific element within a matrix.
- HashMap with Depth-Keyed Traversal: Utilizing a HashMap with depth as the key to perform level traversals in trees (and potentially graphs).
Java comes with its own LinkedHashMap where elements in a map are also linked ( http://www.codingbison.com/java-collections/java-collections-linked-hash-map.html ). LinkedHashMap can be effectively used in the following scenarios:
- LRU (Least Recently Used) Cache: By combining a LinkedHashMap with a fixed capacity, you can maintain the insertion order of elements while efficiently evicting the least recently used items when the cache is full.
- Walking a Tree: When traversing a tree from the root to the leaf nodes, you can use a LinkedHashMap to store the visited nodes in the order of visitation. This allows you to check if a node has been visited or not, as well as print the nodes in the order they were visited.
- First Unique Number: In this scenario, you can utilize a LinkedHashMap to keep track of the unique numbers in a queue. The LinkedHashMap maintains the insertion order of elements and allows efficient lookup for existing keys. The FirstUnique class can be implemented with the following methods:
- FirstUnique(int[] nums): Initializes the object with the numbers in the queue.
- int showFirstUnique(): Returns the value of the first unique integer in the queue. If there is no such integer, it returns -1.
- void add(int value): Inserts the given value to the queue.
- Using a LinkedHashMap for the First Unique Number problem allows for efficient retrieval of the first unique element and preserves the insertion order of elements.