Hash算法:双重散列
双重散列是线性开型寻址散列(开放寻址法)中的冲突解决技术。双重散列使用在发生冲突时将第二个散列函数应用于键的想法。
此算法使用:
(hash1(key) + i * hash2(key)) % TABLE_SIZE
来进行双哈希处理。hash1() 和 hash2() 是哈希函数,而 TABLE_SIZE 是哈希表的大小。当发生碰撞时,我们通过重复增加 步长i 来寻找键。
第一个Hash函数:hash1(key) = key % TABLE_SIZE。
/** * 计算首次的Hash值 * * @param key * @return */ private int hash1(int key) { return (key % TABLE_SIZE); }
第二个Hash函数是:hash2(key) = PRIME – (key % PRIME),其中 PRIME 是小于 TABLE_SIZE 的质数。
/** * 发生碰撞是时继续计算Hash值 * * @param key * @return */ private int hash2(int key) { return (PRIME - (key % PRIME)); }
第二个Hash函数表现好的特征:
绝对不会产生 0 索引
能在整个HashTable 循环探测
计算会快点
与第一个Hash函数互相独立
PRIME 与 TABLE_SIZE 是 “相对质数”
Java实现代码:
package algorithm.hash; /** * 双重哈希 */ public class DoubleHash { private static final int TABLE_SIZE = 13; // 哈希表大小 private static int PRIME = 7; // 散列函数值 private int[] hashTable; private int curr_size; // 当前表中存的元素 public DoubleHash() { this.hashTable = new int[TABLE_SIZE]; this.curr_size = 0; for (int i = 0; i < TABLE_SIZE; i++) hashTable[i] = -1; } private boolean isFull() { return curr_size == TABLE_SIZE; } /** * 计算首次的Hash值 * * @param key * @return */ private int hash1(int key) { return (key % TABLE_SIZE); } /** * 发生碰撞是时继续计算Hash值 * * @param key * @return */ private int hash2(int key) { return (PRIME - (key % PRIME)); } /** * 向Hash表中存值 * * @param key */ private void insertHash(int key) { /* 表是否已满 */ if (isFull()) { return; } /* 获取首次的Hash值 */ int index = hash1(key); // 如果发生碰撞 if (hashTable[index] != -1) { /* 计算第二次的Hash值 */ int index2 = hash2(key); int i = 1; while (true) { /* 再次合成新的地址 */ int newIndex = (index + i * index2) % TABLE_SIZE; // 如果再次寻找时没有发生碰撞,把key存入表中的对应位置 if (hashTable[newIndex] == -1) { hashTable[newIndex] = key; break; } i++; } } else { // 一开始没有发生碰撞 hashTable[index] = key; } curr_size++; // Hash表中当前所存元素数量加1 } /** * 打印Hash表 */ private void displayHash() { for (int i = 0; i < TABLE_SIZE; i++) { if (hashTable[i] != -1) System.out.println(i + " --> " + hashTable[i]); else System.out.println(i); } } public static void main(String[] args) { int[] a = {19, 27, 36, 10, 64}; DoubleHash doubleHash = new DoubleHash(); for (int i = 0; i < a.length; i++) doubleHash.insertHash(a[i]); doubleHash.displayHash(); } }
相关推荐
tuonioooo 2013-08-04
tuonioooo 2011-10-21
gotea 2011-10-14
Broadview 2019-06-26
jkzyx 2020-06-29
TNTMysql工程师 2020-06-16
natloc 2020-06-10
SelinaChan 2020-05-18
ladysosoli 2020-01-19
Happyunlimited 2020-01-12
yedaoxiaodi 2020-01-08
mbcsdn 2020-01-07
lixiaotao 2020-01-03
hanyujianke 2020-01-01
wangshuangbao 2020-07-05
weiguoxin 2020-06-11
JF0 2020-01-24
码墨 2020-01-18
chouliqingke 2019-12-17