文档章节

数据结构与算法07 之哈希表

乐在克里特
 乐在克里特
发布于 2017/02/23 13:52
字数 2553
阅读 5
收藏 0
点赞 0
评论 0

        哈希表也称为散列表,是根据关键字值(key value)而直接进行访问的数据结构。也就是说,它通过把关键字值映射到一个位置来访问记录,以加快查找的速度。这个映射函数称为哈希函数(也称为散列函数),映射过程称为哈希化,存放记录的数组叫做散列表。比如我们可以用下面的方法将关键字映射成数组的下标:arrayIndex = hugeNumber % arraySize。

        哈希化之后难免会产生一个问题,那就是对不同的关键字,可能得到同一个散列地址,即同一个数组下标,这种现象称为冲突,那么我们该如何去处理冲突呢?一种方法是开放地址法,即通过系统的方法找到数组的另一个空位,把数据填入,而不再用哈希函数得到的数组下标,因为该位置已经有数据了;另一种方法是创建一个存放链表的数组,数组内不直接存储数据,这样当发生冲突时,新的数据项直接接到这个数组下标所指的链表中,这种方法叫做链地址法。下面针对这两种方法进行讨论。

1.开放地址法

线性探测法

        所谓线性探测,即线性地查找空白单元。如果21是要插入数据的位置,但是它已经被占用了,那么就是用22,然后23,以此类推。数组下标一直递增,直到找到空白位。下面是基于线性探测法的哈希表实现代码:

 

  1. public class HashTable {  
  2.     private DataItem[] hashArray; //DateItem类是数据项,封装数据信息  
  3.     private int arraySize;  
  4.     private int itemNum; //数组中目前存储了多少项  
  5.     private DataItem nonItem; //用于删除项的  
  6.     public HashTable() {  
  7.         arraySize = 13;  
  8.         hashArray = new DataItem[arraySize];  
  9.         nonItem = new DataItem(-1); //deleted item key is -1  
  10.     }  
  11.     public boolean isFull() {  
  12.         return (itemNum == arraySize);  
  13.     }  
  14.     public boolean isEmpty() {  
  15.         return (itemNum == 0);  
  16.     }  
  17.     public void displayTable() {  
  18.         System.out.print("Table:");  
  19.         for(int j = 0; j < arraySize; j++) {  
  20.             if(hashArray[j] != null) {  
  21.                 System.out.print(hashArray[j].getKey() + " ");  
  22.             }  
  23.             else {  
  24.                 System.out.print("** ");  
  25.             }  
  26.         }  
  27.         System.out.println("");  
  28.     }  
  29.     public int hashFunction(int key) {  
  30.         return key % arraySize;     //hash function  
  31.     }  
  32.       
  33.     public void insert(DataItem item) {  
  34.         if(isFull()) {            
  35.             //扩展哈希表  
  36.             System.out.println("哈希表已满,重新哈希化..");  
  37.             extendHashTable();  
  38.         }  
  39.         int key = item.getKey();  
  40.         int hashVal = hashFunction(key);  
  41.         while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {  
  42.             ++hashVal;  
  43.             hashVal %= arraySize;  
  44.         }  
  45.         hashArray[hashVal] = item;  
  46.         itemNum++;  
  47.     }  
  48.     /* 
  49.      * 数组有固定的大小,而且不能扩展,所以扩展哈希表只能另外创建一个更大的数组,然后把旧数组中的数据插到新的数组中。但是哈希表是根据数组大小计算给定数据的位置的,所以这些数据项不能再放在新数组中和老数组相同的位置上,因此不能直接拷贝,需要按顺序遍历老数组,并使用insert方法向新数组中插入每个数据项。这叫重新哈希化。这是一个耗时的过程,但如果数组要进行扩展,这个过程是必须的。 
  50.      */  
  51.     public void extendHashTable() { //扩展哈希表  
  52.         int num = arraySize;  
  53.         itemNum = 0//重新记数,因为下面要把原来的数据转移到新的扩张的数组中  
  54.         arraySize *= 2//数组大小翻倍  
  55.         DataItem[] oldHashArray = hashArray;  
  56.         hashArray = new DataItem[arraySize];  
  57.         for(int i = 0; i < num; i++) {  
  58.             insert(oldHashArray[i]);  
  59.         }  
  60.     }  
  61.     public DataItem delete(int key) {  
  62.         if(isEmpty()) {  
  63.             System.out.println("Hash table is empty!");  
  64.             return null;  
  65.         }  
  66.         int hashVal = hashFunction(key);  
  67.         while(hashArray[hashVal] != null) {  
  68.             if(hashArray[hashVal].getKey() == key) {  
  69.                 DataItem temp = hashArray[hashVal];  
  70.                 hashArray[hashVal] = nonItem; //nonItem表示空Item,其key为-1  
  71.                 itemNum--;  
  72.                 return temp;  
  73.             }  
  74.             ++hashVal;  
  75.             hashVal %= arraySize;  
  76.         }  
  77.         return null;  
  78.     }  
  79.       
  80.     public DataItem find(int key) {  
  81.         int hashVal = hashFunction(key);  
  82.         while(hashArray[hashVal] != null) {  
  83.             if(hashArray[hashVal].getKey() == key) {  
  84.                 return hashArray[hashVal];  
  85.             }  
  86.             ++hashVal;  
  87.             hashVal %= arraySize;  
  88.         }  
  89.         return null;  
  90.     }  
  91. }  
  92. class DataItem {  
  93.     private int iData;  
  94.     public DataItem (int data) {  
  95.         iData = data;  
  96.     }  
  97.     public int getKey() {  
  98.         return iData;  
  99.     }  
  100. }  

        线性探测有个弊端,即数据可能会发生聚集。一旦聚集形成,它会变得越来越大,那些哈希化后落在聚集范围内的数据项,都要一步步的移动,并且插在聚集的最后,因此使聚集变得更大。聚集越大,它增长的也越快。这就导致了哈希表的某个部分包含大量的聚集,而另一部分很稀疏。

        为了解决这个问题,我们可以使用二次探测:二次探测是防止聚集产生的一种方式,思想是探测相隔较远的单元,而不是和原始位置相邻的单元。线性探测中,如果哈希函数计算的原始下标是x, 线性探测就是x+1, x+2, x+3, 以此类推;而在二次探测中,探测的过程是x+1, x+4, x+9, x+16,以此类推,到原始位置的距离是步数的平方。二次探测虽然消除了原始的聚集问题,但是产生了另一种更细的聚集问题,叫二次聚集:比如讲184,302,420和544依次插入表中,它们的映射都是7,那么302需要以1为步长探测,420需要以4为步长探测, 544需要以9为步长探测。只要有一项其关键字映射到7,就需要更长步长的探测,这个现象叫做二次聚集。二次聚集不是一个严重的问题,但是二次探测不会经常使用,因为还有好的解决方法,比如再哈希法。

再哈希法

        为了消除原始聚集和二次聚集,现在需要的一种方法是产生一种依赖关键字的探测序列,而不是每个关键字都一样。即:不同的关键字即使映射到相同的数组下标,也可以使用不同的探测序列。再哈希法就是把关键字用不同的哈希函数再做一遍哈希化,用这个结果作为步长,对于指定的关键字,步长在整个探测中是不变的,不同关键字使用不同的步长、经验说明,第二个哈希函数必须具备如下特点:

        1. 和第一个哈希函数不同;

        2. 不能输出0(否则没有步长,每次探索都是原地踏步,算法将进入死循环)。

        专家们已经发现下面形式的哈希函数工作的非常好:stepSize = constant - key % constant; 其中constant是质数,且小于数组容量。

        再哈希法要求表的容量是一个质数,假如表长度为15(0-14),非质数,有一个特定关键字映射到0,步长为5,则探测序列是0,5,10,0,5,10,以此类推一直循环下去。算法只尝试这三个单元,所以不可能找到某些空白单元,最终算法导致崩溃。如果数组容量为13, 质数,探测序列最终会访问所有单元。即0,5,10,2,7,12,4,9,1,6,11,3,一直下去,只要表中有一个空位,就可以探测到它。下面看看再哈希法的代码:

 

  1. public class HashDouble {  
  2.     private DataItem[] hashArray;  
  3.     private int arraySize;  
  4.     private int itemNum;  
  5.     private DataItem nonItem;  
  6.     public HashDouble() {  
  7.         arraySize = 13;  
  8.         hashArray = new DataItem[arraySize];  
  9.         nonItem = new DataItem(-1);  
  10.     }  
  11.     public void displayTable() {  
  12.         System.out.print("Table:");  
  13.         for(int i = 0; i < arraySize; i++) {  
  14.             if(hashArray[i] != null) {  
  15.                 System.out.print(hashArray[i].getKey() + " ");  
  16.             }  
  17.             else {  
  18.                 System.out.print("** ");  
  19.             }  
  20.         }  
  21.         System.out.println("");  
  22.     }  
  23.     public int hashFunction1(int key) { //first hash function  
  24.         return key % arraySize;  
  25.     }  
  26.       
  27.     public int hashFunction2(int key) { //second hash function  
  28.         return 5 - key % 5;  
  29.     }  
  30.       
  31.     public boolean isFull() {  
  32.         return (itemNum == arraySize);  
  33.     }  
  34.     public boolean isEmpty() {  
  35.         return (itemNum == 0);  
  36.     }  
  37.     public void insert(DataItem item) {  
  38.         if(isFull()) {  
  39.             System.out.println("哈希表已满,重新哈希化..");  
  40.             extendHashTable();  
  41.         }  
  42.         int key = item.getKey();  
  43.         int hashVal = hashFunction1(key);  
  44.         int stepSize = hashFunction2(key); //用hashFunction2计算探测步数  
  45.         while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {  
  46.             hashVal += stepSize;  
  47.             hashVal %= arraySize; //以指定的步数向后探测  
  48.         }  
  49.         hashArray[hashVal] = item;  
  50.         itemNum++;  
  51.     }  
  52.     public void extendHashTable() {  
  53.         int num = arraySize;  
  54.         itemNum = 0//重新记数,因为下面要把原来的数据转移到新的扩张的数组中  
  55.         arraySize *= 2//数组大小翻倍  
  56.         DataItem[] oldHashArray = hashArray;  
  57.         hashArray = new DataItem[arraySize];  
  58.         for(int i = 0; i < num; i++) {  
  59.             insert(oldHashArray[i]);  
  60.         }  
  61.     }  
  62.     public DataItem delete(int key) {  
  63.         if(isEmpty()) {  
  64.             System.out.println("Hash table is empty!");  
  65.             return null;  
  66.         }  
  67.         int hashVal = hashFunction1(key);  
  68.         int stepSize = hashFunction2(key);  
  69.         while(hashArray[hashVal] != null) {  
  70.             if(hashArray[hashVal].getKey() == key) {  
  71.                 DataItem temp = hashArray[hashVal];  
  72.                 hashArray[hashVal] = nonItem;  
  73.                 itemNum--;  
  74.                 return temp;  
  75.             }  
  76. hashVal += stepSize;  
  77.             hashVal %= arraySize;  
  78.         }  
  79.         return null;  
  80.     }  
  81.     public DataItem find(int key) {  
  82.         int hashVal = hashFunction1(key);  
  83.         int stepSize = hashFunction2(key);  
  84.         while(hashArray[hashVal] != null) {  
  85.             if(hashArray[hashVal].getKey() == key) {  
  86.                 return hashArray[hashVal];  
  87.             }  
  88.             hashVal += stepSize;  
  89.             hashVal %= arraySize;  
  90.         }  
  91.         return null;  
  92.     }  
  93. }  

2.链地址法

        在开放地址法中,通过再哈希法寻找一个空位解决冲突问题,另一个方法是在哈希表每个单元中设置链表(即链地址法),某个数据项的关键字值还是像通常一样映射到哈希表的单元,而数据项本身插入到这个单元的链表中。其他同样映射到这个位置的数据项只需要加到链表中,不需要在原始的数组中寻找空位。下面看看链地址法的代码:

 

  1. public class HashChain {  
  2.     private SortedList[] hashArray; //数组中存放链表  
  3.     private int arraySize;  
  4.     public HashChain(int size) {  
  5.         arraySize = size;  
  6.         hashArray = new SortedList[arraySize];  
  7.         //new出每个空链表初始化数组  
  8.         for(int i = 0; i < arraySize; i++) {  
  9.             hashArray[i] = new SortedList();  
  10.         }  
  11.     }  
  12.     public void displayTable() {  
  13.         for(int i = 0; i < arraySize; i++) {  
  14.             System.out.print(i + ": ");  
  15.             hashArray[i].displayList();  
  16.         }  
  17.     }  
  18.     public int hashFunction(int key) {  
  19.         return key % arraySize;  
  20.     }  
  21.     public void insert(LinkNode node) {  
  22.         int key = node.getKey();  
  23.         int hashVal = hashFunction(key);  
  24.         hashArray[hashVal].insert(node); //直接往链表中添加即可  
  25.     }  
  26.     public LinkNode delete(int key) {  
  27.         int hashVal = hashFunction(key);  
  28.         LinkNode temp = find(key);  
  29.         hashArray[hashVal].delete(key);//从链表中找到要删除的数据项,直接删除  
  30.         return temp;  
  31.     }  
  32.       
  33.     public LinkNode find(int key) {  
  34.         int hashVal = hashFunction(key);  
  35.         LinkNode node = hashArray[hashVal].find(key);  
  36.         return node;  
  37.     }  
  38. }  

    下面是链表类的代码,用的是有序链表:

 

  1. public class SortedList {  
  2.     private LinkNode first;  
  3.     public SortedList() {  
  4.         first = null;  
  5.     }  
  6.     public boolean isEmpty() {  
  7.         return (first == null);  
  8.     }  
  9.     public void insert(LinkNode node) {  
  10.         int key = node.getKey();  
  11.         LinkNode previous = null;  
  12.         LinkNode current = first;  
  13.         while(current != null && current.getKey() < key) {  
  14.             previous = current;  
  15.             current = current.next;  
  16.         }  
  17.         if(previous == null) {  
  18.             first = node;  
  19.         }  
  20.         else {  
  21.             node.next = current;  
  22.             previous.next = node;  
  23.         }  
  24.     }  
  25.     public void delete(int key) {  
  26.         LinkNode previous = null;  
  27.         LinkNode current = first;  
  28.         if(isEmpty()) {  
  29.             System.out.println("chain is empty!");  
  30.             return;  
  31.         }  
  32.         while(current != null && current.getKey() != key) {  
  33.             previous = current;  
  34.             current = current.next;  
  35.         }  
  36.         if(previous == null) {  
  37.             first = first.next;  
  38.         }  
  39.         else {  
  40.             previous.next = current.next;  
  41.         }  
  42.     }  
  43.     public LinkNode find(int key) {  
  44.         LinkNode current = first;  
  45.         while(current != null && current.getKey() <= key) {  
  46.             if(current.getKey() == key) {  
  47.                 return current;  
  48.             }  
  49.             current = current.next;  
  50.         }  
  51.         return null;  
  52.     }  
  53.     public void displayList() {  
  54.         System.out.print("List(First->Last):");  
  55.         LinkNode current = first;  
  56.         while(current != null) {  
  57.             current.displayLink();  
  58.             current = current.next;  
  59.         }  
  60.         System.out.println("");  
  61.     }  
  62. }  
  63. class LinkNode {  
  64.     private int iData;  
  65.     public LinkNode next;  
  66.     public LinkNode(int data) {  
  67.         iData = data;  
  68.     }  
  69.     public int getKey() {  
  70.         return iData;  
  71.     }  
  72.     public void displayLink() {  
  73.         System.out.print(iData + " ");  
  74.     }  
  75. }  

        在没有冲突的情况下,哈希表中执行插入和删除操作可以达到O(1)的时间级,这是相当快的,如果发生冲突了,存取时间就依赖后来的长度,查找或删除时也得挨个判断,但是最差也就O(N)级别。

 

http://blog.csdn.net/eson_15/article/details/51138588

© 著作权归作者所有

共有 人打赏支持
乐在克里特
粉丝 15
博文 265
码字总数 394729
作品 0
杭州
程序员
PHP哈希表碰撞攻击原理

最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷纷中招。本文结合PHP内核源码,聊一聊这种攻击的原理及实现。 哈希表碰撞攻击的基本原理 哈希表是一...

modernizr ⋅ 2014/07/01 ⋅ 5

PHP哈希表碰撞攻击原理

文章出处:http://www.codinglabs.org/html/hash-collisions-attack-on-php.html 最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷纷中招。本文结合P...

鉴客 ⋅ 2012/04/17 ⋅ 0

[译] PHP7 数组:HashTable

http://joshuais.me/yi-php7-shu-zu-hashtable/?utmsource=tuicool&utm_medium=referral [译] PHP7 数组:HashTable November 17, 2016 简介 几乎每个C程序中都会使用到哈希表。鉴于C语言只允......

污湖洞主 ⋅ 2017/06/12 ⋅ 0

分布式一致性哈希环

哈希表的原理与实现 一列键值对数据,存储在一个table中,如何通过数据的关键字快速查找相应值呢?不要告诉我一个个拿出来比较key啊,呵呵。 大家都知道,在所有的线性数据结构中,数组的定位...

tantexian ⋅ 2016/04/07 ⋅ 0

狮子的魂/celib

celib是使用ANSI C开发的一个扩展类库(c extend library),包含了一些常用的数据结构和算法的封装,可以用于应用或者学习。 目前已经包含的封装如下: (01). 动态数组。 (02). bitmap。 (03)...

狮子的魂 ⋅ 2014/09/13 ⋅ 0

想要明白什么是key/value数据库

想要明白什么是key/value数据库,就必须了解哈希表(Hash Table)这种数据结构。 比如,Berkley DB就是典型的key/value数据库。 以下内容对哈希表进行了很形象的描述: ====================...

fir01 ⋅ 2013/09/24 ⋅ 0

什么叫哈希表(转载)

google搜索到的头条:散列表(也叫哈希表),是根据关键码值直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数...

云栖希望。 ⋅ 2017/12/04 ⋅ 0

C 扩展类库--celib

celib 是使用ANSI C开发的一个扩展类库(c extend library),包含了一些常用的数据结构和算法的封装,可以应用到项目或者用于学习。 目前已经包含的封装如下: (01). 动态数组。 (02). bitmap...

狮子的魂 ⋅ 2014/01/03 ⋅ 0

基于暴雪的哈希算法,实现可扩展的哈希表

前提:基于暴雪的哈希算法,http://www.oschina.net/code/snippet997671217 这里参考了RyanLee的代码,想基于这个源码,实现可扩展的哈希表。 查看源代码后,发现能够将哈希表上的所有空间都...

你条草 ⋅ 2012/04/11 ⋅ 7

谁知道这个 simHash 的二层哈希表 是什么东西???

任意两个电影间的相似度是固定值, 不会随着时间而改变。 所 以我们可以利用“用空间换取时间”的思想, 事先计算出每两个电影间相似度并 保存在特定的数据结构里。 如此一来, 算法需要电影...

sca7 ⋅ 2017/04/07 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

马氏距离与欧氏距离

马氏距离 马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。 如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧氏距离,如果协方差矩阵为对角阵,则其也...

漫步当下 ⋅ 昨天 ⋅ 0

聊聊spring cloud的RequestRateLimiterGatewayFilter

序 本文主要研究一下spring cloud的RequestRateLimiterGatewayFilter GatewayAutoConfiguration @Configuration@ConditionalOnProperty(name = "spring.cloud.gateway.enabled", matchIfMi......

go4it ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部