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

This article introduces the relevant knowledge of "how to implement Map based on zipper hash table and linear probe hash table". In the operation of actual cases, many people will encounter this dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Hash function

The first step in implementing a hash table is to consider how to convert a key to the subscript of an array. In this case, you need to use a hash function to convert the key value to an integer and then use the method of dividing the remainder to calculate the subscript of the array. We need a different hash function for each type of key.

HashCode has been implemented for commonly used data types in java, so we only need to use the method of dividing the remainder according to the value of hashCode to convert to the subscript of the array.

The convention in java: if the equals of two objects is equal, then the hashCode must be the same; if the hashCode is the same, the equals is not necessarily the same. For custom-type keys, we usually need to customize the implementation hashCode and equals;. The default hashCode returns the memory address of the object, which is not a good hash value.

Let me take a look at the common types of hashCode calculations in Java.

Integer

Because the value that hashCode needs to return is an int value, the hashCode implementation of Integer is simple and returns the current value directly.

@ Override public int hashCode () {return Integer.hashCode (value);} public static int hashCode (int value) {return value;} Long

The hashCode calculation of Long type in Java is to shift the value unsigned 32 bits to the right, then to disagree with the value, to ensure that each bit is used, and finally to force the conversion to an int value.

@ Override public int hashCode () {return Long.hashCode (value);} public static int hashCode (long value) {return (int) (value ^ (value > 32));} Double, Float

The implementation of hashCode in floating-point key java is to represent the key as binary.

Public static int hashCode (float value) {return floatToIntBits (value);} public static int floatToIntBits (float value) {int result = floatToRawIntBits (value); / / Check for NaN based on values of bit fields, maximum / / exponent and nonzero significand. If (result & FloatConsts.EXP_BIT_MASK) = = FloatConsts.EXP_BIT_MASK) & & (result & FloatConsts.SIGNIF_BIT_MASK)! = 0) result = 0x7fc00000; return result;} String

Each char in java can be represented as an int value, so the string is converted to an int value

Public int hashCode () {int h = hash; if (h = = 0 & & value.length > 0) {char val [] = value; for (int I = 0; I

< value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }软缓存 如果计算一个散列值比较耗时，那么我可以这个计算好的值缓存起来，即使用一个变量把这个值保存起来，在下一次调用时直接返回。Java中的String就是采用的这种方式。 拉链式的散列表 散列函数能够将键值转换成数组的下标;第二步就是需要处理碰撞冲突，也就是需要处理遇到了两个散列值相同的对象应该如何存储。有一种方式是数组中的每一个元素都指向一个链表用来存放散列值相同的对象，这种方式被称为拉链法 拉链法可以使用原始的链表保存键，也可以采用我们之前实现的红黑树来表示，在java8中采用的这两种方式的混合，在节点数超过了8之后变为红黑树。 这里我们就采用简单的链表来实现拉链式散列表，数据结构使用在前几篇中已经实现的LinkedMap，可以参考前面的文章《基于数组或链表实现Map》。

Public class SeparateChainingHashMap implements Map {private int size; private LinkedMap [] table; public SeparateChainingHashMap (int capacity) {this.table = (LinkedMap []) new LinkedMap [capacity]; for (int I = 0; I

< capacity; i++) { this.table[i] = new LinkedMap(); } } @Override public void put(K key, V value) { this.table[hash(key)].put(key, value); size++; } private int hash(K key) { return (key.hashCode() & 0x7fffffff) % table.length; } @Override public V get(K key) { return this.table[hash(key)].get(key); } @Override public void delete(K key) { this.table[hash(key)].delete(key); size--; } @Override public int size() { return size; } } 这的hash函数使用key的hashCode与上0x7fffffff得到一个非负的整数，然后再使用除留余数法计算出数组的下标。其中0x7FFFFFFF 的二进制表示就是除了首位是 0，其余都是1，也就是说，这是最大的整型数 int(因为第一位是符号位，0 表示他是正数),可以使用Integer.MAX_VALUE代替 散列表的主要目的在于把键值均匀的分布到数组中，所以散列表是无序的，如果你需要的Map需要支持取出最大值，最小值，那么散列表都不适合。 这里我们实现的拉链式散列表的数组大小是固定的，但是通常在随着数据量的增大，越短的数组出现碰撞的几率会增大，所以需要数组支持动态的扩容，扩容之后需要把原来的值重新插入到扩容之后的数组中。数组的扩容可以参考之前的文章《老哥是时候来复习下数据结构与算法了》 线性探测式散列表 实现散列表的另一种方式就是用大小为M来保存N个键值，其中M>

To resolve collision conflicts, you need to make use of spaces in the array; the simplest implementation in this way is linear detection.

The main idea of linear detection: when you insert a key and directly add one to the index to check the next location after a collision conflict, three situations occur:

The next position is equal to the key to be inserted, then the value modifies the value

The next location is not equal to the key to be inserted, so the index adds one to continue searching.

If the next position is still an empty space, put the object to be inserted directly into the empty space

Initialization

Linear probe hash tables use two arrays to store keys and values,capacity to represent the size of the initialization array

Private int size; private int capacity; private K [] keys; private V [] values; public LinearProbingHashMap (int capacity) {this.capacity = capacity; this.keys = (K []) new Object [capacity]; this.values = (V []) new Object [capacity];}

insert

When the position of the insert key exceeds the size of the array, you need to go back to the beginning of the array and continue searching until you find one with a position of null; index = (index + 1)% capacity

When the stored capacity of the array is more than half of the total capacity of the array, it needs to be expanded to twice the original capacity.

@ Override public void put (K key, V value) {if (Objects.isNull (key)) {throw new IllegalArgumentException ("Key can not null");} if (this.size > this.capacity / 2) {resize (2 * this.capacity);} int index; for (index = hash (key); this.keys [index]! = null Index = (index + 1)% capacity) {if (this.keys [index] .equals (key)) {this.values [index] = value; return;}} this.keys [index] = key; this.values [index] = value; size++;}

Dynamically resize the array

We can refer to the dynamic resizing data implemented in the article "it's time to review the data structure and algorithm"; in linear detection, we need to reinsert the original data into the expanded data, because the size of the array has changed and the location of the index needs to be recalculated.

Private void resize (int cap) {LinearProbingHashMap linearProbingHashMap = new LinearProbingHashMap (cap); for (int I = 0; I

< capacity; i++) { linearProbingHashMap.put(keys[i], values[i]); } this.keys = linearProbingHashMap.keys; this.values = linearProbingHashMap.values; this.capacity = linearProbingHashMap.capacity; } 查询 线性探测散列表中实现查询的思路：根据待查询key的hash函数计算出索引的位置，然后开始判断当前位置上的key是否和待查询key相等，如果相等那么就直接返回value，如果不相等那么就继续查找下一个索引直到遇到某个位置是null才结束，表示查询的key不存在; @Override public V get(K key) { if (Objects.isNull(key)) { throw new IllegalArgumentException("Key can not null"); } int index; for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) { if (this.keys[index].equals(key)) { return this.values[index]; } } return null; } 删除元素 线性探测式的删除稍微麻烦一些，首先需要查找出待删除的元素位置，删除元素之后需要把当前索引之后的连续位置上的元素重新插入;因为是否有空位对于线性探测式散列表的查找至关重要;例如：5->

7-> 9. After deleting 7, if the position of 7 is empty without reinserting 7, then the get method will not be able to query 9.

After each deletion, you need to detect the number of actual elements in the array. If there is a big difference with the capacity of the array, you can reduce the size of the array.

@ Override public void delete (K key) {if (Objects.isNull (key)) {throw new IllegalArgumentException ("Key can not null");} int index; for (index = hash (key); this.keys [index]! = null; index = (index + 1)% capacity) {if (this.keys [index] .equals (key)) {this.keys [index] = null This.values [index] = null; break;}} for (index = (index + 1)% capacity; this.keys [index]! = null; index = (index + 1)% capacity) {this.size--; this.put (this.keys [index], this.values [index]); this.keys [index] = null; this.values [index] = null } this.size--; if (size > 0 & & size < capacity / 4) {resize (capacity / 2);}} "how to implement Map based on zipper and linear probe hash tables" ends here. Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.