数据结构(Java语言)——HashTable(开放定址法)简

作者:武汉味美食家餐饮管理有限公司 来源:www.cj17917.com 发布时间:2017-09-03 12:36:07
数据结构(Java语言)——HashTable(开放定址法)简单实现

分离链接散列算法的缺点是使用一些链表。由于给新单元分配地址需要时间,因此这就导致算法的速度有些减慢,同时算法实际上还要求对第二种数据结构的实现。另有一种不用链表解决冲突的方法是尝试另外一些单元,直到找出空的单元为止。更常见的是,单元h0(x),h1(x),h2(x),...相继被试选,其中hi(x)=(hash(x)+f(i)) mod TableSize,且f(0)=0。函数f是冲突解决方法,因为所有的数据都要置于表内,所以这种解决方案所需要的表要比分离链接散列的表大。一般来说,对于不使用分离链接的散列表来说,其装填因子λ应该低于 0.5。我们把这样的表叫做探测散列表(probing hash table)。现在我们就来考察三中通常的冲突解决方案。

线性探测法 在线性探测法中,函数f是i的线性函数,典型情况是f(i)=i。这相当于相继探测逐个单元(必要时可回绕)以查找出一个空单元。只要表足够大,总能够找到一个自由单元,但是如此花费的时间是相当多的。而且即使表相对较空,这样占据的单元也会开始形成一些区块,其结果次称为一次聚集,就是说,散列到区块中的任何关键字都需要多次试选单元才能够解决冲突,然后该关键字被添加到相应的区块中。 可以证明,使用线性探测的预期探测次数对于插入和不成功的查找来说大约为0.5(1+1/(1-λ)²),而对于成功的查找来说则是0.5(1+1/(1-λ))。从程序中容易看出,插入和不成功查找需要相同次数的探测,成功查找应该比不成功查找平均花费较少的时间。 平方探测法 平方探测是消除线性探测中一次聚集问题的冲突解决方法。平方探测就是冲突函数为二次的探测方法。流行的选择是f(i)=i²。对于线性探测,让散列表几乎填满元素并不是个好主意,因为此时表的性能会降低。对于平方探测情况甚至更糟:一旦表被填充超过一半,当表的大小不是素数时甚至在表被填充一半之前,就不能保证一次找到空的单元了。这是因为最多有表的一半可以用作解决冲突的备选位置。 可以证明,即使表被填充的位置仅仅比一半多一个,那么插入都有可能失败。另外,表的大小是素数也很重要,如果表的大小不是素数,那么备选单元的个数可能会锐减。 在探测散列表中标准的删除操作不能自行,因为相应的单元可能已经引起过冲突,元素绕过它存在了别处。因此,探测散列表需要懒惰删除。 虽然平方散列排除了一次聚集,但是散列到同一位置上的那些元素将探测相同的备选单元,这叫做二次聚集。二次聚集是理论上的一个小缺憾,模拟结果指出,对每次查找,它一般要引起另外的少于一半的探测。下面的技术将会排除这个缺憾,不过这要付出计算一个附加的散列函数的代价。 双散列 对于双散列,一种流行的选择是f(i)=i*hash?(x)。这个公式是说,我们将第二个散列函数应用到x并在距离hash?(x),2hash?(x),...等处探测。hash?(x)选择得不好将会是灾难性的。函数一定不要算得0值,另外保证所有的单元都能被探测到也是很重要的。诸如hash?(x)=R-(x mod R)这样的函数将起到良好的作用,其中R为小于TableSize的素数。 在使用双散列时保证表的大小为素数时很重要的,如果表的大小不是素数,那么备选单元就有可能提前用完。然而,如果双散列正确实现,则模拟表明,预期的探测次数几乎和随机冲突解决方法的情况相同,这使得双散列理论上很有吸引力。不过,平方探测不需要使用第二个散列函数,从而在实践中使用可能更简单并且更快,特别对于像串这样的关键字,他们的散列函数计算起来相当耗时。
以下是一个平方探测法的散列表实现: import java.util.Random; public class QuadraticProbingHashTable { private static final int DEFAULT_TBALE_SIZE = 11; private HashEntry[] array; private int currentSize; /* * 三种情况:null,非null且该项为活动的,非null且该项被标记删除 */ private static class HashEntry { public AnyType element; public boolean isActive; public HashEntry(AnyType e) { this(e, true); } public HashEntry(AnyType e, boolean i) { element = e; isActive = i; } } public QuadraticProbingHashTable() { this(DEFAULT_TBALE_SIZE); } public QuadraticProbingHashTable(int size) { array = new HashEntry[size]; makeEmpty(); } public void makeEmpty() { for (int i = 0; i < array.length; i++) { array[i] = null; } currentSize = 0; } /** * 哈希表是否包含某元素 * * @param x * 查询元素 * @return 查询结果 */ public boolean contains(AnyType x) { int currentPos = findPos(x); return isActive(currentPos); } /** * 向哈希表中插入某元素,若存在则不操作 * * @param x * 插入元素 */ public void insert(AnyType x) { int currentPos = findPos(x); System.out.println(x + hash-> + currentPos); if (isActive(currentPos)) { return; } array[currentPos] = new HashEntry(x, true); if (++currentSize > array.length / 2) { rehash(); } } /** * 向哈希表中懒惰删除某元素 * * @param x * 删除元素 */ public void remove(AnyType x) { int currentPos = findPos(x); if (isActive(currentPos)) { array[currentPos].isActive = false; } } /** * 通过哈希算法找到某元素下标(平方探测法):f(i)=f(i-1)+2i-1 * * @param x * 查找元素 * @return 该元素在数组中下标 */ private int findPos(AnyType x) { int offset = 1; int currentPos = myhash(x); while (array[currentPos] != null && !array[currentPos].element.equals(x)) { currentPos += offset; offset += 2; if (currentPos >= array.length) { currentPos -= array.length; } } return currentPos; } /** * 检查指定下标是否存在活动项 * * @param currentPos * 下标 * @return 是否有活动项 */ private boolean isActive(int currentPos) { return array[currentPos] != null && array[currentPos].isActive; } /** * 简单的哈希算法 * * @param x * 元素 * @return 哈希值 */ private int myhash(AnyType x) { int hashVal = x.hashCode(); hashVal %= array.length; if (hashVal < 0) { hashVal += array.length; } return hashVal; } /** * 再散列函数,插入空间过半时执行 */ @SuppressWarnings(unchecked) private void rehash() { HashEntry[] oldArray = array; // 创建一个容量翻倍的空表 array = new HashEntry[nextPrime(2 * array.length)]; currentSize = 0; // 将数据复制到新表 for (int i = 0; i < oldArray.length; i++) { if (oldArray[i] != null && oldArray[i].isActive) { insert(oldArray[i].element); } } System.out.println( rehash by length of: + array.length); } /** * 检查某整数是否为素数 * * @param num * 检查整数 * @return 检查结果 */ private static boolean isPrime(int num) { if (num == 2 || num == 3) { return true; } if (num == 1 || num % 2 == 0) { return false; } for (int i = 3; i * i <= num; i += 2) { if (num % i == 0) { return false; } } return true; } /** * 返回不小于某个整数的素数 * * @param num * 整数 * @return 下一个素数(可以相等) */ private static int nextPrime(int num) { if (num == 0 || num == 1 || num == 2) { return 2; } if (num % 2 == 0) { num++; } while (!isPrime(num)) { num += 2; } return num; } public void printTable() { for (int i = 0; i < array.length; i++) { System.out.println(-----); if (array[i] != null) { System.out.println(array[i].element + ); } else { System.out.println(); } } } public static void main(String[] args) { QuadraticProbingHashTable hashTable = new QuadraticProbingHashTable(); Random random = new Random(); for (int i = 0; i < 20; i++) { hashTable.insert(random.nextInt(60)); } hashTable.printTable(); } }
执行结果:
22 hash-> 0
15 hash-> 4
45 hash-> 1
33 hash-> 9
45 hash-> 1
17 hash-> 6
32 hash-> 10
22 hash-> 22
45 hash-> 0
15 hash-> 15
17 hash-> 17
33 hash-> 10
32 hash-> 9


rehash by length of: 23
19 hash-> 19
3 hash-> 3
9 hash-> 13
17 hash-> 17
12 hash-> 12
48 hash-> 2
45 hash-> 0
58 hash-> 16
45 hash-> 45
48 hash-> 1
3 hash-> 3
32 hash-> 32
33 hash-> 33
12 hash-> 12
9 hash-> 9
15 hash-> 15
58 hash-> 11
17 hash-> 17
19 hash-> 19
22 hash-> 22


rehash by length of: 47
3 hash-> 3
44 hash-> 44
27 hash-> 27
57 hash-> 10
44 hash-> 44
-----

-----
48
-----

-----
3
-----

-----

-----

-----

-----

-----
9
-----
57
-----
58
-----
12
-----

-----

-----
15
-----

-----
17
-----

-----
19
-----

-----

-----
22
-----

-----

-----

-----

-----
27
-----

-----

-----

-----

-----
32
-----
33
-----

-----

-----

-----

-----

-----

-----

-----

-----

-----

-----
44
-----
45
-----


企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网站制作 http://wuhan.666rj.com

  • 上一篇:用python阐释工作量证明(proof of work)
  • 下一篇:最后一页
  • 
    COPYRIGHT © 2015 武汉味美食家餐饮管理有限公司 ALL RIGHTS RESERVED.
    本站所有原创信息,未经许可请勿任意转载或复制使用 网站地图 技术支持:肥猫科技
    精彩专题:网站建设
    购买本站友情链接、项目合作请联系客服QQ:2500-38-100