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

This article will explain in detail the example analysis of the hash table in Java. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

1, concept

In the sequential structure and balance tree, there is no corresponding relationship between the element key and its storage location, so when looking for an element, it must go through multiple key code comparisons. The time complexity of sequential search is O (N), and the height of the tree in the balanced tree is O (). The efficiency of search depends on the number of comparisons of elements in the search process.

Ideal search method: you can get the elements you want to search for directly from the table at one time without any comparison. If you construct a storage structure through a function (hashFunc) to establish an one-to-one mapping relationship between the storage location of the element and its key, then the element can be quickly found through this function when looking for it.

When in the structure:

Insert element

According to the key of the element to be inserted, this function calculates the storage location of the element and stores it according to this location.

Search element

Do the same calculation for the key of the element, take the value of the function as the storage position of the element, and compare the elements in the structure according to this position. If the keys are equal, the search is successful.

For example: data set {1, 7, 6, 4, 5, 9}

The hash function is set to: hash (key) = key% capacity; capacity is the total size of the underlying space of the storage element.

2, conflict-avoidance

First of all, we need to make it clear that because the capacity of the underlying array of our hash table is often less than the actual number of keywords to be stored, which leads to a problem, conflicts are inevitable, but what we can do is to reduce the conflict rate as much as possible.

3, conflict-avoidance-hash function design

Common hash function

Direct customization method-(commonly used)

Take a linear function of the keyword as the hash address: Hash (Key) = A*Key + B advantages: simple, uniform disadvantages: need to know the distribution of key words in advance use scenarios: suitable for finding relatively small and continuous situations

The method of division and residue-(commonly used)

Let the number of addresses allowed in the hash table be m, and take a prime number p that is not greater than m but closest to or equal to m as the divisor, according to the hash function: Hash (key) = key% p (p = 0.75) {resize ();}} public int get (int key) {/ / whatever way it is stored, then take 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 void resize () {Node [] newArray = new Node [2*this.array.length]; for (int I = 0; I

< this.array.length; i++){ Node cur = array[i]; Node curNext = null; while (cur != null){ curNext = cur.next; int index = cur.key % newArray.length; cur.next = newArray[i]; newArray[i] = cur; cur = curNext.next; cur = curNext; } } this.array = newArray; }7，完整代码 class HashBucket { static class 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]; this.usedSize = 0; } public void put(int key,int val) { //1、确定下标 int index = key % this.array.length; //2、遍历这个下标的链表 Node cur = array[index]; while (cur != null) { //更新val if(cur.key == key) { cur.val = val; return; } cur = cur.next; } //3、cur == null 当前数组下标的 链表 没要key Node node = new Node(key,val); node.next = array[index]; array[index] = node; this.usedSize++; //4、判断 当前 有没有超过负载因子 if(loadFactor() >

) {/ / expand resize ();}} public int get (int key) {/ / int index = key% this.array.length; Node cur = array [index] While (cur! = null) {if (cur.key = = key) {return cur.val;} cur = cur.next;} return-1Accord /} public double loadFactor () {return this.usedSize*1.0 / this.array.length } public void resize () {Node [] newArray = new Node [2*this.array.length]; for (int I = 0; I < this.array.length; iTunes +) {Node cur = array [I]; Node curNext = null; while (cur! = null) {curNext = cur.next; int index = cur.key% newArray.length Cur.next = newArray [I]; newArray [I] = cur; cur = curNext.next; cur = curNext;}} this.array = newArray }} this is the end of the article on "sample analysis of hash tables in Java". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

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.