哈希表是什么？哈希表数据结构详细资料分析.doc
哈希表是什么？哈希表数据结构详细资料分析我所写的这些数据结构，都是比较经典的，也是面试中经常会出现的，这篇文章我就不闲扯了，全是干货，如果你能读完，希望对你有所帮助 哈希表也称为散列表，是根据关键字值（key value）而直接进行访问的数据结构。也就是说，它通过把关键字值映射到一个位置来访问记录，以加快查找的速度。这个映射函数称为哈希函数（也称为散列函数），映射过程称为哈希化，存放记录的数组叫做散列表。比如我们可以用下面的方法将关键字映射成数组的下标：arrayIndex=hugeNumber%arraySize那么问题来了，这种方式对不同的关键字，可能得到同一个散列地址，即同一个数组下标，这种现象称为冲突，那么我们该如何去处理冲突呢？一种方法是开放地址法，即通过系统的方法找到数组的另一个空位，把数据填入，而不再用哈希函数得到的数组下标，因为该位置已经有数据了；另一种方法是创建一个存放链表的数组，数组内不直接存储数据，这样当发生冲突时，新的数据项直接接到这个数组下标所指的链表中，这种方法叫做链地址法。下面针对这两种方法进行讨论。1.开放地址法1.1 线性探测法所谓线性探测，即线性地查找空白单元。我举个例子，如果21是要插入数据的位置，但是它已经被占用了，那么就是用22，然后23，以此类推。数组下标一直递增，直到找到空白位。下面是基于线性探测法的哈希表实现代码：publicclassHashTable privateDataItem hashArray; /DateItem类是数据项，封装数据信息privateint arraySize;privateint itemNum; /数组中目前存储了多少项privateDataItem nonItem; /用于删除项的publicHashTable() arraySize = 13;hashArray = newDataItemarraySize;nonItem = newDataItem(-1); /deleted item key is -1publicboolean isFull() return (itemNum = arraySize);publicboolean isEmpty() return (itemNum = 0);publicvoid displayTable() System.out.print("Table:");for(int j = 0; j +hashVal;hashVal %= arraySize;hashArrayhashVal = item;itemNum+;/* 数组有固定的大小，而且不能扩展，所以扩展哈希表只能另外创建一个更大的数组，然后把旧数组中的数据插到新的数组中。但是哈希表是根据数组大小计算给定数据的位置的，所以这些数据项不能再放在新数组中和老数组相同的位置上，因此不能直接拷贝，需要按顺序遍历老数组，并使用insert方法向新数组中插入每个数据项。这叫重新哈希化。这是一个耗时的过程，但如果数组要进行扩展，这个过程是必须的。*/publicvoid extendHashTable() /扩展哈希表int num = arraySize;itemNum = 0; /重新记数，因为下面要把原来的数据转移到新的扩张的数组中arraySize *= 2; /数组大小翻倍DataItem oldHashArray = hashArray;hashArray = newDataItemarraySize;for(int i = 0; i aItemdelete(int key) if(isEmpty() System.out.println("Hash table is empty!");returnnull;int hashVal = hashFunction(key);while(hashArrayhashVal != null) if(hashArrayhashVal.getKey() = key) DataItem temp = hashArrayhashVal;hashArrayhashVal = nonItem; /nonItem表示空Item,其key为-1itemNum-;return temp;+hashVal;hashVal %= arraySize;returnnull;publicDataItem find(int key) int hashVal = hashFunction(key);while(hashArrayhashVal != null) if(hashArrayhashVal.getKey() = key) return hashArrayhashVal;+hashVal;hashVal %= arraySize;returnnull;classDataItem privateint iData;publicDataItem (int data) iData = data;publicint getKey() return iData;线性探测有个弊端，即数据可能会发生聚集。一旦聚集形成，它会变得越来越大，那些哈希化后落在聚集范围内的数据项，都要一步步的移动，并且插在聚集的最后，因此使聚集变得更大。聚集越大，它增长的也越快。这就导致了哈希表的某个部分包含大量的聚集，而另一部分很稀疏。为了解决这个问题，我们可以使用二次探测：二次探测是防止聚集产生的一种方式，思想是探测相隔较远的单元，而不是和原始位置相邻的单元。线性探测中，如果哈希函数计算的原始下标是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,一直下去，只要表中有一个空位，就可以探测到它。下面看看再哈希法的代码：publicclassHashDouble privateDataItem hashArray;privateint arraySize;privateint itemNum;privateDataItem nonItem;publicHashDouble() arraySize = 13;hashArray = newDataItemarraySize;nonItem = newDataItem(-1);publicvoid displayTable() System.out.print("Table:");for(int i = 0; i hashVal += stepSize;hashVal %= arraySize; /以指定的步数向后探测hashArrayhashVal = item;itemNum+;publicvoid extendHashTable() int num = arraySize;itemNum = 0; /重新记数，因为下面要把原来的数据转移到新的扩张的数组中arraySize *= 2; /数组大小翻倍DataItem oldHashArray = hashArray;hashArray = newDataItemarraySize;for(int i = 0; i previous = current;current = current.next;if(previous = null) first = node;else node.next = current;previous.next = node;publicvoiddelete(int key) LinkNode previous = null;LinkNode current = first;if(isEmpty() System.out.println("chain is empty!");return;while(current != null ">previous = current;current = current.next;if(previous = null) first = first.next;else previous.next = current.next;publicLinkNode find(int key) LinkNode current = first;while(current != null ">if(current.getKey() = key) return current;current = current.next;returnnull;publicvoid displayList() System.out.print("List(First->Last):");LinkNode current = first;while(current != null) current.displayLink();current = current.next;System.out.println("");classLinkNode privateint iData;publicLinkNode next;publicLinkNode(int data) iData = data;publicint getKey() return iData;publicvoid displayLink() System.out.print(iData + " ");在没有冲突的情况下，哈希表中执行插入和删除操作可以达到O(1)的时间级，这是相当快的，如果发生冲突了，存取时间就依赖后来的长度，查找或删除时也得挨个判断，但是最差也就O(N)级别。
