1. 哈希表: 它是一种数据结构, 可以提供快速的插入操作和查找操作如果哈希表中有多少数据项, 插入和删除操作只需要接近常量的时间即 O(1)的时间级在计算机中如果需要一秒内查找上千条记录, 通常使用哈希表哈希表的速度明显比树快, 编程实现也相对容易但哈希表是基于数组的, 数组创建后难于扩展某些哈希表被填基本填满后性能下降的非常严重, 所以程序员必须清除表中需要存储多少数据, 而且也没有简便的方式以任意一种顺序 (如由大到小) 遍历表中的数据项, 如果需要这种能力, 只能选择其他数据结构
2. 哈希化: 把关键字转化成数组下标的过程称为哈希化在哈希表中这个转换通过哈希函数来完成而对于特定的关键字, 并不需要哈希函数, 关键字的值可以直接作为数组下标
3. 冲突: 把巨大的数字空间压缩成较小的数字空间必然要付出代价, 即不能保证每个单词都映射到数组的空白单元假设要在数组中插入单词 cat, 通过哈希函数得到它的数组下标后, 发现那个单元已经有一个单词了, 对于特定大小的数组, 这种情况称为冲突冲突使得哈希化的方案无法实施, 解决的方案有两种, 一种是通过系统的方法找到数组的一个空位, 并把单词填入, 而不再用哈希函数得到的下标, 这种方法称为开放地址法, 第二种方案是创建一个存放单词链表的数组, 数组不直接用来存储单词, 这样发生冲突时, 新的数据项就直接插入这个数组下标所指向的链表中, 这种方法称为链地址法
3-1. 开放地址法的具体实现有三种不同方案, 线性探测, 二次探测和再哈希法
3-1-1. 线性探测: 在线性探测中, 线性的查找空白单元, 如果 5421 是要插入的数据位置, 它已被占用, 那么就使用 5422, 然后是 5423, 依次类推, 直到找到这个空位
3-1-1-1. 存在的问题: 会出现聚集情况也叫原始聚集
3-1-2. 二次探测: 二次探测是防止聚集产生的一种尝试, 思想是探测相隔较远的单元而不知和原始单元相邻的单元在二次探测中, 探测的过程是 x+1,x+4,x+9,x+16....
3-1-2-1. 问题: 存在二次聚集
3-1-3. 再哈希法: 为了消除原始聚集和二次聚集, 引入了再哈希法, 二次聚集产生的原因是, 二次探测的算法产生的探测序列步长总是固定的: 1,4,9,16... 现在需要一 种方法是依赖关键字的探测序列, 方法是把关键字用相同的哈希函数再做一次哈希化, 用这个结果作为步长, 对指定的关键字步长在整个探测过程中是不变的, 第二个哈希函数必须具备以下特点: a. 和第一个哈希函数不同, b. 不能输出 0(否则就没有步长, 将先入死循环)专家发现类似于 stepsize = constant - (key % constant)的形式工作的很好, 其中个 constant 是质数, 且小于数组容量(stepsize = 5 - (key % 5)), 这种方案最为常用
3-2. 链地址法图示:
3-2-1. 缺点: 链地址法在概念上比开放地址法简单, 但是代码可能要比其他的长, 因为要包含链表机制, 这就要求在程序中增加一个类
4. 再哈希法实现代码:
4.1.DataItem.java
- package com.cn.hashtable;
- /**
- * 再哈希法
- * @author Administrator
- *
- */
- public class DataItem {
- private int iData;
- public DataItem(int id){
- iData = id;
- }
- public int getkey(){
- return iData;
- }
- }
- View Code
- 4.2.HashTable.java
- package com.cn.hashtable;
- /**
- * 哈希表算法开放地址法 --- 再哈希实现
- * @author Administrator
- *
- */
- public class HashTable {
- private DataItem[] hashArray;
- private int arraySize;
- private DataItem nonItem;
- HashTable(int size){
- arraySize = size;
- hashArray = new DataItem[arraySize];
- nonItem = new DataItem(-1);
- }
- public void displayTable(){
- System.out.print("Table:");
- for (int i = 0; i < arraySize; i++) {
- if (hashArray[i] != null)
- System.out.print(hashArray[i].getkey()+" ");
- else
- System.out.print("**");
- }
- System.out.println("");
- }
- public int hashFunc1(int key){
- return key % arraySize;
- }
- public int hashFunc2(int key){
- return 5 - key % 5;
- }
- public void insert(int key,DataItem item){
- int hashval = hashFunc1(key);
- int stepsize = hashFunc2(key);
- while (hashArray[hashval] != null && hashArray[hashval].getkey() != 1){
- hashval += stepsize;
- hashval %= arraySize;
- }
- hashArray[hashval] = item;
- }
- public DataItem delete(int key){
- int hashval = hashFunc1(key);
- int stepsize = hashFunc2(key);
- while (hashArray[hashval] != null){
- if (hashArray[hashval].getkey() == key){
- DataItem temp = hashArray[hashval];
- hashArray[hashval] = nonItem;
- return temp;
- }
- hashval += stepsize;
- hashval %= arraySize;
- }
- return null;
- }
- public DataItem find(int key){
- int hashval = hashFunc1(key);
- int stepsize = hashFunc2(key);
- while (hashArray[hashval] != null){
- if (hashArray[hashval].getkey() == key)
- return hashArray[hashval];
- hashval += stepsize;
- hashval %= arraySize;
- }
- return null;
- }
- }
- View Code
- 4.3.HTTest.java
- package com.cn.hashtable;
- /**
- * 测试类
- * @author Administrator
- *
- */
- public class HTTest {
- public static void main(String[] args) {
- HashTable t = new HashTable(10);
- t.insert(1, new DataItem(1));
- t.insert(2, new DataItem(2));
- t.insert(4, new DataItem(3));
- t.insert(3, new DataItem(4));
- t.insert(2, new DataItem(5));
- t.insert(9, new DataItem(6));
- t.displayTable();
- t.delete(9);
- System.out.println(t.find(9));
- }
- }
- View Code
5. 链地址法实现:
5.1.Link.java
- package com.cn.hashtable;
- /**
- * 链地址法实现
- * @author Administrator
- *
- */
- public class Link {
- public int iData;
- public Link next;
- public Link(int it){
- iData = it;
- }
- public int getkey(){
- return iData;
- }
- public void displayLink(){
- System.out.print(iData+" ");
- }
- }
- View Code
- 5.2.SortedList.java
- package com.cn.hashtable;
- public class SortedList {
- private Link first;
- public void insert(Link thelink){
- int key = thelink.getkey();
- Link previous = null;
- Link current = first;
- while (current != null && key > current.getkey()){
- previous = current;
- current = current.next;
- }
- if (previous == null)
- first = thelink;
- else
- previous.next = thelink;
- thelink.next = current;
- }
- public void delete(int key){
- Link previous = null;
- Link current = first;
- while (current != null && key != current.getkey()){
- previous = current;
- current = current.next;
- }
- if (previous == null)
- first = first.next;
- else
- previous.next = current.next;
- }
- public Link find(int key){
- Link current = first;
- while (current != null && current.getkey() <= key){
- if (current.getkey() == key)
- return current;
- current = current.next;
- }
- return null;
- }
- public void displayList(){
- System.out.print("list:first-->last:");
- Link current = first;
- while (current != null){
- current.displayLink();
- current = current.next;
- }
- System.out.println("");
- }
- }
- View Code
- 5.3.LHashTable.java
- package com.cn.hashtable;
- /**
- * 链地址法实现哈希表类
- * @author Administrator
- *
- */
- public class LHashTable {
- private SortedList[] hashArray;
- private int arraySize;
- public LHashTable(int size){
- arraySize = size;
- hashArray = new SortedList[arraySize];
- for (int i = 0; i < arraySize; i++) {
- hashArray[i] = new SortedList();
- }
- }
- public void display(){
- for (int i = 0; i < arraySize; i++) {
- System.out.print(i+".");
- hashArray[i].displayList();
- }
- System.out.println("");
- }
- public int hashFunc(int key){
- return key % arraySize;
- }
- public void insert(Link thelink){
- int key = thelink.getkey();
- int hashval = hashFunc(key);
- hashArray[hashval].insert(thelink);
- }
- public void delete(int key){
- int hashval = hashFunc(key);
- hashArray[hashval].delete(key);
- }
- public Link find(int key){
- int hashval = hashFunc(key);
- Link thelink = hashArray[hashval].find(key);
- return thelink;
- }
- }
- View Code
- 5.4.LHTTest.java
- package com.cn.hashtable;
- /**
- * 链地址法实现测试类
- * @author Administrator
- *
- */
- public class LHTTest {
- public static void main(String[] args) {
- LHashTable lt = new LHashTable(10);
- for (int i = 0; i < 5; i++) {
- lt.insert(new Link(i));
- }
- lt.display();
- }
- }
- View Code
6. 哈希化的效率: 在哈希表中执行插入和搜索操作可以达到 O(1)的时间级, 如果没有遇到冲突, 就只需要使用一次哈希函数和数组的引用这是最小的存取时间级如果发生冲突, 存取时间就依赖后边的探测长度因此, 一次的查找或插入操作与探测长度成正比, 平均探测长度取决于装填因子(表中项数和表长的比率), 随着填装因子变大, 探测长度也越来越长
6.1. 线性探测时, 探测序列 (p) 和填装因子 (L) 的关系: 成功查找: P = (1 + 1/(1 - L)^2)/2; 不成功查找:(1 + 1/(1 - L))/2, 随着装填因子变小, 存储效率下降而速度上升
6.2. 二次探测和再哈希法: 对成功的搜索公式是:-log2(1 - loadfactor)/loadfactor; 不成功的查找: 1/(1-loadfactor)
6.3. 假设哈希表含有 arraySize 个数据项, 每个数据项有一个链表, 在表中有 N 个数据项: averageListLength = N/arraySize; 成功查找: 1+loadfactor/2; 不成功的查找: 1+loadfactor
来源: http://www.bubuko.com/infodetail-2504332.html