Hashing Flashcards
(5 cards)
What is Hashing and when is it used?
Hashing uses hash tables for fast lookup or grouping.
Use case includes frequency counting, grouping, and caching.
Example: LRU Cache.
What are the key steps in Hashing?
- Initialize hash table for data.
- Store/retrieve with key-value pairs.
- Handle collisions or updates.
Explain steps for LRU Cache aloud.
How does Hashing apply to LRU Cache?
The problem is to implement least recently used cache. The approach is to use a hash table and doubly linked list for O(1) operations.
Verbalize solution logic for LRU Cache aloud.
What are the complexity and gotchas of Hashing?
Time complexity is O(1) average, and space complexity is O(n).
Gotchas include capacity=0 and frequent evictions.
List edge cases for LRU Cache aloud.
Code example of Hashing.
```python
from typing import Optional
class Node:
def __init__(self, key: int = 0, value: int = 0) -> None:
self.key = key
self.value = value
self.prev: Optional[‘Node’] = None
self.next: Optional[‘Node’] = None
class LRUCache:
def __init__(self, capacity: int) -> None:
self.capacity = capacity
self.cache: dict[int, Node] = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add(node)
return node.value
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self._add(node)
self.cache[key] = node
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
def _add(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
~~~
Sketch cache structure on paper.