【面试算法笔记】0302-哈希表-哈希表实现

个人主页https://github.com/zbhgis前言本系列主要记录自己学习算法的过程中的感悟。力扣705. 设计哈希集合链接https://leetcode.cn/problems/design-hashset/description/注意点代码简单数组class MyHashSet { boolean[] nodes new boolean[1000009]; public void add(int key) { nodes[key] true; } public void remove(int key) { nodes[key] false; } public boolean contains(int key) { return nodes[key]; } }链表解法class MyHashSet { private static final int BASE 769; private LinkedListInteger[] data; public MyHashSet() { data new LinkedList[BASE]; for (int i 0; i BASE; i ) { data[i] new LinkedList(); } } private int hash(int key) { return key % BASE; } public void add(int key) { int h hash(key); if (!data[h].contains(key)) { data[h].add(key); } } public void remove(int key) { int h hash(key); data[h].remove((Integer) key); } public boolean contains(int key) { int h hash(key); return data[h].contains(key); } } /** * Your MyHashSet object will be instantiated and called as such: * MyHashSet obj new MyHashSet(); * obj.add(key); * obj.remove(key); * boolean param_3 obj.contains(key); */时空复杂度分析力扣706. 设计哈希映射链接https://leetcode.cn/problems/design-hashmap/description/注意点代码简单数组class MyHashMap { int INF Integer.MAX_VALUE; int N 1000009; int[] map new int[N]; public MyHashMap() { Arrays.fill(map, INF); } public void put(int key, int value) { map[key] value; } public int get(int key) { return map[key] INF ? -1 : map[key]; } public void remove(int key) { map[key] INF; } }链表解法class MyHashMap { private static final int BASE 769; private class Node { int key; int value; Node next; Node(int key, int value) { this.key key; this.value value; } } private Node[] buckets; public MyHashMap() { buckets new Node[BASE]; } private int hash(int key) { return key % BASE; } public void put(int key, int value) { int h hash(key); Node head buckets[h]; Node cur head; while (cur ! null) { if (cur.key key) { cur.value value; return; } cur cur.next; } Node newNode new Node(key, value); newNode.next head; buckets[h] newNode; } public int get(int key) { int h hash(key); Node cur buckets[h]; while (cur ! null) { if (cur.key key) { return cur.value; } cur cur.next; } return -1; } public void remove(int key) { int h hash(key); Node head buckets[h]; if (head ! null head.key key) { buckets[h] head.next; return; } Node prev head; Node cur head null ? null : head.next; while (cur ! null) { if (cur.key key) { prev.next cur.next; return; } prev cur; cur cur.next; } } } /** * Your MyHashMap object will be instantiated and called as such: * MyHashMap obj new MyHashMap(); * obj.put(key,value); * int param_2 obj.get(key); * obj.remove(key); */时空复杂度分析参考https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html