Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to realize the basic function of hash table by Java". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to realize the basic function of hash table by Java".

1. Insert the element / * user:ypc by inserting the hash header. * date:2021-05-20; * time: 11 public int key; int value; Node next; Node 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 and 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;}} 2.Hash table insertion / / JDK1.8 is tail interpolation 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; if (last = = null) {array [index] = node; this.usedSize++ Return;} last.next = node; this.usedSize++; if (loadFactor () > 0.75) {resize2 ();}} III. Expansion of 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)); }}六、哈希表的泛型实现public class HashBuck2 { static class Node { public K key; public V val; public Node next; public Node(K key, V val) { this.key = key; this.val = val; } } public Node[] array; public int usedSize; public HashBuck2() { this.array = (Node[]) new Node[8]; } public void put(K key, V val) { int hash = key.hashCode(); int index = hash % array.length; Node cur = array[index]; while (cur != null) { if (cur.key.equals(key)) { cur.val = val; return; } cur = cur.next; } Node node = new Node(key, val); node.next = array[index]; array[index] = node; this.usedSize++; if (loadFactor() >

{resize ();}} public V get (K key) {int hash = key.hashCode (); int index = hash% array.length; Node 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; iTunes +) {Node cur = array [I] While (cur! = null) {int hash = cur.key.hashCode (); int index = hash% array.length; Node 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 public int id; Student 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 hashBuck2 = new HashBuck2 (); Student S1 = new Student (10001); Student S2 = new Student (10001); Student S3 = new Student (10003); hashBuck2.put (S1 Mague 89); hashBuck2.put (S1 Mague 60); hashBuck2.put (S2 Mague 94) HashBuck2.put (s3100); System.out.println (hashBuck2.get (S1)); System.out.println (hashBuck2.get (S2));}}

Note:

To use a custom class as the key or HashSet value of HashMap, you must override the hashCode and equals square methods, and to make equals equal objects, hashCode must be consistent.

For example, Student S1 is the same as the id of S2, but you get a different value, so you have to overwrite the hashCode and equals methods. If you don't overwrite them, you use the hashCode and equals methods of the Object class, comparing the addresses.

Why did JDK1.7 and before use head insertion while JDK1.8 used tail insertion

Hashmap uses array + linked list. The array is of fixed length. If the linked list is too long, you need to expand the length of the array and reduce the length of the linked list by rehash. If two threads trigger capacity expansion at the same time, when the node is moved, it will cause two nodes in a linked list to refer to each other, resulting in a linked list.

At this point, I believe you have a deeper understanding of "how to achieve the basic functions of the hash table in Java". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.