Java實現哈希表的基本功能
一、哈希表頭插法放入元素
/** * user:ypc; * date:2021-05-20; * time: 11:05; */ public class HashBuck { class Node { public int key; int value; Node next; Node(int key, int value) { this.key = key; this.value = value; } } public int usedSize; public Node[] array; HashBuck() { this.array = new Node[8]; this.usedSize = 0; } //JDk1.7及之前是頭插法 public void put1(int key, int value) { int index = key % this.array.length; Node node = new Node(key, value); Node cur = array[index]; while (cur != null) { if (cur.key == key) { cur.value = value; return; } cur = cur.next; } node.next = array[index]; array[index] = node; this.usedSize++; if (loadFactor() > 0.75) { resize1(); } } public double loadFactor() { return this.usedSize / this.array.length * 1.0; } }
二、哈希表尾插法放入元素
//JDK1.8是尾插法 public Node findLast(Node head) { if (head == null) return head; Node cur = head; while (cur.next != null) { cur = cur.next; } return cur; } public void put2(int key, int value) { int index = key % this.array.length; Node node = new Node(key, value); Node cur = array[index]; while (cur != null) { if (cur.key == key) { cur.value = value; return; } cur = cur.next; } Node last = findLast(array[index]); if (last == null) { array[index] = node; this.usedSize++; return; } last.next = node; this.usedSize++; if (loadFactor() > 0.75) { resize2(); } }
三、哈希表頭插、尾插擴容
public void resize1() { Node[] newArray = new Node[this.array.length * 2]; for (int i = 0; i < this.array.length; i++) { Node cur = array[i]; while (cur != null) { int index = cur.key % newArray.length; Node curNext = cur.next; cur.next = newArray[index]; newArray[index] = cur; cur = curNext; } } this.array = newArray; } //resize尾插 public void resize2() { Node[] newArray = new Node[this.array.length * 2]; for (int i = 0; i < this.array.length; i++) { Node cur = array[i]; while (cur != null) { int index = cur.key % newArray.length; Node curNext = cur.next; Node last = findLast(newArray[index]); if (last == null) { newArray[index] = cur; break; } last.next = cur; cur = curNext; } } this.array = newArray; } public Node findLast(Node head) { if (head == null) return head; Node cur = head; while (cur.next != null) { cur = cur.next; } return cur; }
四、找到key對應的value
public int get(int key) { int index = key % this.array.length; Node cur = this.array[index]; while (cur != null) { if (cur.key == key) { return cur.value; } cur = cur.next; } return -1; }
五、運行結果
class HashBuckTest { public static void main(String[] args) { HashBuck hashBuck = new HashBuck(); //頭插 hashBuck.put1(9,451); hashBuck.put1(17,455); //尾插 //hashBuck.put2(9,451); //hashBuck.put2(17,455); hashBuck.put1(2,45); hashBuck.put1(3,14); hashBuck.put1(4,52); hashBuck.put1(4,89); System.out.println(hashBuck.get(1)); System.out.println("+================="); } }
頭插
尾插
擴容
class HashBuckTest { public static void main(String[] args) { HashBuck hashBuck = new HashBuck(); // hashBuck.put1(9, 451); // hashBuck.put1(17, 455); hashBuck.put1(1, 589); hashBuck.put1(2, 45); hashBuck.put1(3, 14); hashBuck.put1(4, 52); hashBuck.put1(4, 1); hashBuck.put1(6, 829); hashBuck.put1(7, 72); hashBuck.put1(8, 8279); hashBuck.put2(9,451); hashBuck.put2(15,455); hashBuck.put2(31,451); System.out.println(hashBuck.get(7)); System.out.println(hashBuck.get(4)); System.out.println(hashBuck.get(15)); System.out.println(hashBuck.get(31)); } }
get
六、哈希表的泛型實現
public class HashBuck2<K, V> { static class Node<K, V> { public K key; public V val; public Node<K, V> next; public Node(K key, V val) { this.key = key; this.val = val; } } public Node<K, V>[] array; public int usedSize; public HashBuck2() { this.array = (Node<K, V>[]) new Node[8]; } public void put(K key, V val) { int hash = key.hashCode(); int index = hash % array.length; Node<K, V> cur = array[index]; while (cur != null) { if (cur.key.equals(key)) { cur.val = val; return; } cur = cur.next; } Node<K, V> node = new Node<>(key, val); node.next = array[index]; array[index] = node; this.usedSize++; if (loadFactor() > 0.75) { resize(); } } public V get(K key) { int hash = key.hashCode(); int index = hash % array.length; Node<K, V> cur = array[index]; while (cur != null) { if (cur.key.equals(key)) { return cur.val; } cur = cur.next; } return null; } public void resize() { Node[] newArray = new Node[this.array.length * 2]; for (int i = 0; i < this.array.length; i++) { Node<K,V> cur = array[i]; while (cur != null) { int hash = cur.key.hashCode(); int index = hash % array.length; Node <K,V>curNext = cur.next; cur.next = newArray[index]; newArray[index] = cur; cur = curNext; } } this.array = newArray; } public double loadFactor() { return this.usedSize / this.array.length * 1.0; } }
/** * user:ypc; * date:2021-05-20; * time: 15:25; */ class Student{ public int id; Student(int id){ this.id = id; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return id == student.id; } @Override public int hashCode() { return Objects.hash(id); } } class HashBuck2Test{ public static void main(String[] args) { HashBuck2<Student,Integer> hashBuck2 = new HashBuck2<>(); Student s1 = new Student(10001); Student s2 = new Student(10001); Student s3 = new Student(10003); hashBuck2.put(s1,89); hashBuck2.put(s1,60); hashBuck2.put(s2,94); hashBuck2.put(s3,100); System.out.println(hashBuck2.get(s1)); System.out.println(hashBuck2.get(s2)); } }
註意:
要用自定義類作為 HashMap 的 key 或者 HashSet 的值,必須覆寫 hashCode 和 equals 方 法,而且要做到 equals 相等的對象,hashCode 一定是一致的。
比如Student s1 和 s2 的id一樣,得到的卻是不同的value,所以要覆寫hashCode 和 equals 方 法,如果不覆寫,則使用的是Object類的hashCode 和 equals 方 法,比較的是地址。
重寫之後
七、為什麼JDK1.7及之前使用頭插法而JDK1.8使用尾插法
hashmap用數組+鏈表。數組是固定長度,鏈表太長就需要擴充數組長度進行rehash減少鏈表長度。如果兩個線程同時觸發擴容,在移動節點時會導致一個鏈表中的2個節點相互引用,從而生成環鏈表
到此這篇關於Java實現哈希表的基本功能的文章就介紹到這瞭,更多相關哈希表基本功能實現內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Java 數據結構哈希算法之哈希桶方式解決哈希沖突
- Java數據結構之順序表和鏈表精解
- Java 中 hashCode() 與 equals() 的關系(面試)
- 重寫equals的同時為何要重寫hashCode?
- Java集合-HashMap