• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

读完这篇,希望你能真正理解什么是哈希表

技术杂谈 勤劳的小蚂蚁 2个月前 (01-14) 55次浏览 已收录 0个评论 扫描二维码

哈希表也称为散列表,是根据关键字值(key value)而直接进行访问的数据结构。也就是说,它通过把关键字值映射到一个位置来访问记录,以加快查找的速度。这个映射函数称为哈希函数(也称为散列函数),映射过程称为哈希化,存放记录的数组叫做散列表。比如我们可以用下面的方法将关键字映射成数组的下标:
arrayIndex=hugeNumber%arraySize
那么问题来了,这种方式对不同的关键字,可能得到同一个散列地址,即同一个数组下标,这种现象称为冲突,那么我们该如何去处理冲突呢?一种方法是开放地址法,即通过系统的方法找到数组的另一个空位,把数据填入,而不再用哈希函数得到的数组下标,因为该位置已经有数据了;另一种方法是创建一个存放链表的数组,数组内不直接存储数据,这样当发生冲突时,新的数据项直接接到这个数组下标所指的链表中,这种方法叫做链地址法。下面针对这两种方法进行讨论。

1.开放地址法

1.1 线性探测法

所谓线性探测,即线性地查找空白单元。我举个例子,如果21是要插入数据的位置,但是它已经被占用了,那么就是用22,然后23,以此类推。数组下标一直递增,直到找到空白位。下面是基于线性探测法的哈希表实现代码:
  1. publicclassHashTable {
  2.    privateDataItem[] hashArray; //DateItem类是数据项,封装数据信息
  3.    privateint arraySize;
  4.    privateint itemNum; //数组中目前存储了多少项
  5.    privateDataItem nonItem; //用于删除项的
  6.    publicHashTable() {
  7.        arraySize = 13;
  8.        hashArray = newDataItem[arraySize];
  9.        nonItem = newDataItem(-1); //deleted item key is -1
  10.    }
  11.    publicboolean isFull() {
  12.        return (itemNum == arraySize);
  13.    }
  14.    publicboolean isEmpty() {
  15.        return (itemNum == 0);
  16.    }
  17.    publicvoid 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.    publicint hashFunction(int key) {
  30.        return key % arraySize;     //hash function
  31.    }
  32.    publicvoid insert(DataItem item) {
  33.        if(isFull()) {          
  34.            //扩展哈希表
  35.            System.out.println("哈希表已满,重新哈希化..");
  36.            extendHashTable();
  37.        }
  38.        int key = item.getKey();
  39.        int hashVal = hashFunction(key);
  40.        while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
  41.            ++hashVal;
  42.            hashVal %= arraySize;
  43.        }
  44.        hashArray[hashVal] = item;
  45.        itemNum++;
  46.    }
  47.    /*
  48.     * 数组有固定的大小,而且不能扩展,所以扩展哈希表只能另外创建一个更大的数组,然后把旧数组中的数据插到新的数组中。但是哈希表是根据数组大小计算给定数据的位置的,所以这些数据项不能再放在新数组中和老数组相同的位置上,因此不能直接拷贝,需要按顺序遍历老数组,并使用insert方法向新数组中插入每个数据项。这叫重新哈希化。这是一个耗时的过程,但如果数组要进行扩展,这个过程是必须的。
  49.     */
  50.    publicvoid extendHashTable() { //扩展哈希表
  51.        int num = arraySize;
  52.        itemNum = 0; //重新记数,因为下面要把原来的数据转移到新的扩张的数组中
  53.        arraySize *= 2; //数组大小翻倍
  54.        DataItem[] oldHashArray = hashArray;
  55.        hashArray = newDataItem[arraySize];
  56.        for(int i = 0; i < num; i++) {
  57.            insert(oldHashArray[i]);
  58.        }
  59.    }
  60.    publicDataItemdelete(int key) {
  61.        if(isEmpty()) {
  62.            System.out.println("Hash table is empty!");
  63.            returnnull;
  64.        }
  65.        int hashVal = hashFunction(key);
  66.        while(hashArray[hashVal] != null) {
  67.            if(hashArray[hashVal].getKey() == key) {
  68.                DataItem temp = hashArray[hashVal];
  69.                hashArray[hashVal] = nonItem; //nonItem表示空Item,其key为-1
  70.                itemNum--;
  71.                return temp;
  72.            }
  73.            ++hashVal;
  74.            hashVal %= arraySize;
  75.        }
  76.        returnnull;
  77.    }
  78.    publicDataItem find(int key) {
  79.        int hashVal = hashFunction(key);
  80.        while(hashArray[hashVal] != null) {
  81.            if(hashArray[hashVal].getKey() == key) {
  82.                return hashArray[hashVal];
  83.            }
  84.            ++hashVal;
  85.            hashVal %= arraySize;
  86.        }
  87.        returnnull;
  88.    }
  89. }
  90. classDataItem {
  91.    privateint iData;
  92.    publicDataItem (int data) {
  93.        iData = data;
  94.    }
  95.    publicint getKey() {
  96.        return iData;
  97.    }
  98. }

线性探测有个弊端,即数据可能会发生聚集。一旦聚集形成,它会变得越来越大,那些哈希化后落在聚集范围内的数据项,都要一步步的移动,并且插在聚集的最后,因此使聚集变得更大。聚集越大,它增长的也越快。这就导致了哈希表的某个部分包含大量的聚集,而另一部分很稀疏。
为了解决这个问题,我们可以使用二次探测:二次探测是防止聚集产生的一种方式,思想是探测相隔较远的单元,而不是和原始位置相邻的单元。线性探测中,如果哈希函数计算的原始下标是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. publicclassHashDouble {
  2.    privateDataItem[] hashArray;
  3.    privateint arraySize;
  4.    privateint itemNum;
  5.    privateDataItem nonItem;
  6.    publicHashDouble() {
  7.        arraySize = 13;
  8.        hashArray = newDataItem[arraySize];
  9.        nonItem = newDataItem(-1);
  10.    }
  11.    publicvoid 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.    publicint hashFunction1(int key) { //first hash function
  24.        return key % arraySize;
  25.    }
  26.    publicint hashFunction2(int key) { //second hash function
  27.        return5 - key % 5;
  28.    }
  29.    publicboolean isFull() {
  30.        return (itemNum == arraySize);
  31.    }
  32.    publicboolean isEmpty() {
  33.        return (itemNum == 0);
  34.    }
  35.    publicvoid insert(DataItem item) {
  36.        if(isFull()) {
  37.            System.out.println("哈希表已满,重新哈希化..");
  38.            extendHashTable();
  39.        }
  40.        int key = item.getKey();
  41.        int hashVal = hashFunction1(key);
  42.        int stepSize = hashFunction2(key); //用hashFunction2计算探测步数
  43.        while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
  44.            hashVal += stepSize;
  45.            hashVal %= arraySize; //以指定的步数向后探测
  46.        }
  47.        hashArray[hashVal] = item;
  48.        itemNum++;
  49.    }
  50.    publicvoid extendHashTable() {
  51.        int num = arraySize;
  52.        itemNum = 0; //重新记数,因为下面要把原来的数据转移到新的扩张的数组中
  53.        arraySize *= 2; //数组大小翻倍
  54.        DataItem[] oldHashArray = hashArray;
  55.        hashArray = newDataItem[arraySize];
  56.        for(int i = 0; i < num; i++) {
  57.            insert(oldHashArray[i]);
  58.        }
  59.    }
  60.    publicDataItemdelete(int key) {
  61.        if(isEmpty()) {
  62.            System.out.println("Hash table is empty!");
  63.            returnnull;
  64.        }
  65.        int hashVal = hashFunction1(key);
  66.        int stepSize = hashFunction2(key);
  67.        while(hashArray[hashVal] != null) {
  68.            if(hashArray[hashVal].getKey() == key) {
  69.                DataItem temp = hashArray[hashVal];
  70.                hashArray[hashVal] = nonItem;
  71.                itemNum--;
  72.                return temp;
  73.            }
  74. hashVal += stepSize;
  75.            hashVal %= arraySize;
  76.        }
  77.        returnnull;
  78.    }
  79.    publicDataItem find(int key) {
  80.        int hashVal = hashFunction1(key);
  81.        int stepSize = hashFunction2(key);
  82.        while(hashArray[hashVal] != null) {
  83.            if(hashArray[hashVal].getKey() == key) {
  84.                return hashArray[hashVal];
  85.            }
  86.            hashVal += stepSize;
  87.            hashVal %= arraySize;
  88.        }
  89.        returnnull;
  90.    }
  91. }

2. 链地址法

在开放地址法中,通过再哈希法寻找一个空位解决冲突问题,另一个方法是在哈希表每个单元中设置链表(即链地址法),某个数据项的关键字值还是像通常一样映射到哈希表的单元,而数据项本身插入到这个单元的链表中。其他同样映射到这个位置的数据项只需要加到链表中,不需要在原始的数组中寻找空位。下面看看链地址法的代码:
  1. publicclassHashChain {
  2.    privateSortedList[] hashArray; //数组中存放链表
  3.    privateint arraySize;
  4.    publicHashChain(int size) {
  5.        arraySize = size;
  6.        hashArray = newSortedList[arraySize];
  7.        //new出每个空链表初始化数组
  8.        for(int i = 0; i < arraySize; i++) {
  9.            hashArray[i] = newSortedList();
  10.        }
  11.    }
  12.    publicvoid displayTable() {
  13.        for(int i = 0; i < arraySize; i++) {
  14.            System.out.print(i + ": ");
  15.            hashArray[i].displayList();
  16.        }
  17.    }
  18.    publicint hashFunction(int key) {
  19.        return key % arraySize;
  20.    }
  21.    publicvoid insert(LinkNode node) {
  22.        int key = node.getKey();
  23.        int hashVal = hashFunction(key);
  24.        hashArray[hashVal].insert(node); //直接往链表中添加即可
  25.    }
  26.    publicLinkNodedelete(int key) {
  27.        int hashVal = hashFunction(key);
  28.        LinkNode temp = find(key);
  29.        hashArray[hashVal].delete(key);//从链表中找到要删除的数据项,直接删除
  30.        return temp;
  31.    }
  32.    publicLinkNode find(int key) {
  33.        int hashVal = hashFunction(key);
  34.        LinkNode node = hashArray[hashVal].find(key);
  35.        return node;
  36.    }
  37. }

下面是链表类的代码,用的是有序链表:
  1. publicclassSortedList {
  2.    privateLinkNode first;
  3.    publicSortedList() {
  4.        first = null;
  5.    }
  6.    publicboolean isEmpty() {
  7.        return (first == null);
  8.    }
  9.    publicvoid 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.    publicvoiddelete(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.    publicLinkNode 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.        returnnull;
  52.    }
  53.    publicvoid 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. classLinkNode {
  64.    privateint iData;
  65.    publicLinkNode next;
  66.    publicLinkNode(int data) {
  67.        iData = data;
  68.    }
  69.    publicint getKey() {
  70.        return iData;
  71.    }
  72.    publicvoid displayLink() {
  73.        System.out.print(iData + " ");
  74.    }
  75. }

在没有冲突的情况下,哈希表中执行插入和删除操作可以达到O(1)的时间级,这是相当快的,如果发生冲突了,存取时间就依赖后来的长度,查找或删除时也得挨个判断,但是最差也就O(N)级别。
哈希表就分享这么多,本文建议收藏,在等班车的时候、吃饭排队的时候可以拿出来看看。利用碎片化时间来学习!



丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:读完这篇,希望你能真正理解什么是哈希表
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00