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

This article mainly introduces the relevant knowledge of how to use Java hash bucket to solve the hash conflict, the content is detailed and easy to understand, the operation is simple and quick, and has a certain reference value. I believe you will gain something after reading this article on how to use Java hash bucket to solve hash conflict. Let's take a look.

one。 Implementation form 1 (key-value pairs can only be integers)

We can first implement a relatively simple hash table, using the method of solving hash conflicts in java, that is, hash bucket (open hash). Note:

Nodes can be defined using inner classes

The load factor defaults to 0.75

Because we use a hash bucket to solve the hash conflict, after our successful expansion, the data in the original bucket has to be re-hashed to calculate the new location, otherwise the location of the data in the original bucket will be different from that in the original bucket.

The related code is as follows

Public class HashBucket {static class Node {/ / define node public int key; public int val; public Node next; public Node (int key, int val) {this.key = key; this.val = val;}} private Node [] array; public int usedSize; public HashBucket () {this.array = new Node [10] using inner class method This.usedSize = 0;} public void put (int key,int val) {/ / store data / / 1, determine the subscript int index = key% this.array.length; / / 2, traverse the linked list of the subscript Node cur = array [index] While (cur! = null) {/ / Update val if (cur.key = = key) {cur.val = val; return;} cur = cur.next;} / / 3, cur = = null there is no key Node node = new Node (key,val) in the linked list of the current array subscript Node.next = array [index]; array [index] = node; this.usedSize++; / / 4, determine whether the load factor if (loadFactor () > = 0.75) {/ / load factor we think is 0.75 / / expand resize () }} public int get (int key) {/ / retrieve the data / / take out the data in whatever way int index = key% this.array.length; Node cur = array [index]; while (cur! = null) {if (cur.key = = key) {return cur.val } cur = cur.next;} return-1;} public double loadFactor () {/ / calculate load factor return this.usedSize*1.0 / this.array.length;} public void resize () {/ / expansion function / / create a new 2x array Node [] newArray = new Node [2*this.array.length] / / traversing the original hash bucket / / the outermost loop control array subscript for (int I = 0; I < this.array.length; iTunes +) {Node cur = array [I]; Node curNext = null; while (cur! = null) {/ / record cur.next curNext = cur.next / / the subscript int index = cur.key% newArray.length; / / in the new array cur.next = newArray [index]; newArray [index] = cur; cur = curNext;}} this.array = newArray;} II. Implementation method 2 (improved version)

The key-value pairs in the hash table we implemented above can only store integer data, but generics are needed for more complex types, such as strings, objects, and so on. Note:

You can also use inner classes to define node types

Use generics

The hashCode method is used when converting generics to integers

Use the hash value of the object to determine the subscript. In order to prevent the hash value from being too large, the length of the% array should be allowed.

When traversing the array subscript, use the equals method to compare whether the key is the same

When storing custom data types, be sure to override the hashcode and equals methods

The related code is as follows

Class Person {public String id; public Person (String id) {this.id = id;} @ Override public String toString () {return "Person {" + "id='" + id +'\'+'}';} @ Override public boolean equals (Object o) {if (this = = o) return true If (o = = null | | getClass ()! = o.getClass () return false; Person person = (Person) o; return Objects.equals (id, person.id);} @ Override public int hashCode () {return Objects.hash (id);}} 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 = (Node []) new Node [10]; public int usedSize; public void put (K key,V val) {/ / locate the array subscript int hash = key.hashCode () through the hashcode method; int index = hash% this.array.length Node cur = array [index]; while (cur! = null) {/ / equals is used to traverse whether the subscript key of the current array is the same if (cur.key.equals (key)) {cur.val = val;} cur = cur.next;} Node node = new Node (key,val) Node.next = array [index]; array [index] = node; this.usedSize++;} public V get (K key) {int hash = key.hashCode (); int index = hash% this.array.length; Node cur= array [index]; while (cur! = null) {if (cur.key.equals (key)) {return cur.val } cur = cur.next;} return null;} this is the end of the article on "how to solve hash conflicts with Java hash buckets". Thank you for reading! I believe you all have a certain understanding of "how to use Java hash bucket to solve hash conflicts". If you want to learn more, you are welcome to follow the industry information channel.

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.