首页 注册 登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
TradingView
广告
nishengwu
V2EX  ›  程序员

读完这篇，希望你能真正理解哈希表

  •   
  •   nishengwu · 2018-12-03 22:17:31 +08:00 · 711 次点击
    这是一个创建于 1986 天前的主题，其中的信息可能已经有所发展或是发生改变。

    哈希表是面试中经常会出现的，这篇文章总结一下哈希表中的相关知识，希望对大家有所帮助。

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

    arrayIndex = hugeNumber % arraySize

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

    1. 开放地址法

    1.1 线性探测法

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

    public class HashTable {
	private DataItem[] hashArray; //DateItem 类是数据项，封装数据信息
	private int arraySize;
	private int itemNum; //数组中目前存储了多少项
	private DataItem nonItem; //用于删除项的
	public HashTable() {
		arraySize = 13;
		hashArray = new DataItem[arraySize];
		nonItem = new DataItem(-1); //deleted item key is -1
	}
	public boolean isFull() {
		return (itemNum == arraySize);
	}
	public boolean isEmpty() {
		return (itemNum == 0);
	}
	public void displayTable() {
		System.out.print("Table:");
		for(int j = 0; j < arraySize; j++) {
			if(hashArray[j] != null) {
				System.out.print(hashArray[j].getKey() + " ");
			}
			else {
				System.out.print("** ");
			}
		}
		System.out.println("");
	}
	public int hashFunction(int key) {
		return key % arraySize;  	//hash function
	}
	
	public void insert(DataItem item) {
		if(isFull()) {			
			//扩展哈希表
			System.out.println("哈希表已满，重新哈希化..");
			extendHashTable();
		}
		int key = item.getKey();
		int hashVal = hashFunction(key);
		while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
			++hashVal;
			hashVal %= arraySize;
		}
		hashArray[hashVal] = item;
		itemNum++;
	}
	/*
	 * 数组有固定的大小，而且不能扩展，所以扩展哈希表只能另外创建一个更大的数组，然后把旧数组中的数据插到新的数组中。但是哈希表是根据数组大小计算给定数据的位置的，所以这些数据项不能再放在新数组中和老数组相同的位置上，因此不能直接拷贝，需要按顺序遍历老数组，并使用 insert 方法向新数组中插入每个数据项。这叫重新哈希化。这是一个耗时的过程，但如果数组要进行扩展，这个过程是必须的。
	 */
	public void extendHashTable() { //扩展哈希表
		int num = arraySize;
		itemNum = 0; //重新记数，因为下面要把原来的数据转移到新的扩张的数组中
		arraySize *= 2; //数组大小翻倍
		DataItem[] oldHashArray = hashArray;
		hashArray = new DataItem[arraySize];
		for(int i = 0; i < num; i++) {
			insert(oldHashArray[i]);
		}
	}
	public DataItem delete(int key) {
		if(isEmpty()) {
			System.out.println("Hash table is empty!");
			return null;
		}
		int hashVal = hashFunction(key);
		while(hashArray[hashVal] != null) {
			if(hashArray[hashVal].getKey() == key) {
				DataItem temp = hashArray[hashVal];
				hashArray[hashVal] = nonItem; //nonItem 表示空 Item,其 key 为-1
				itemNum--;
				return temp;
			}
			++hashVal;
			hashVal %= arraySize;
		}
		return null;
	}
	
	public DataItem find(int key) {
		int hashVal = hashFunction(key);
		while(hashArray[hashVal] != null) {
			if(hashArray[hashVal].getKey() == key) {
				return hashArray[hashVal];
			}
			++hashVal;
			hashVal %= arraySize;
		}
		return null;
	}
}
class DataItem {
	private int iData;
	public DataItem (int data) {
		iData = data;
	}
	public int 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 再哈希法

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

    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,一直下去，只要表中有一个空位，就可以探测到它。下面看看再哈希法的代码：

    public class HashDouble {
	private DataItem[] hashArray;
	private int arraySize;
	private int itemNum;
	private DataItem nonItem;
	public HashDouble() {
		arraySize = 13;
		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 hashFunction1(int key) { //first hash function
		return key % arraySize;
	}
	
	public int hashFunction2(int key) { //second hash function
		return 5 - key % 5;
	}
	
	public boolean isFull() {
		return (itemNum == arraySize);
	}
	public boolean isEmpty() {
		return (itemNum == 0);
	}
	public void insert(DataItem item) {
		if(isFull()) {
			System.out.println("哈希表已满，重新哈希化..");
			extendHashTable();
		}
		int key = item.getKey();
		int hashVal = hashFunction1(key);
		int stepSize = hashFunction2(key); //用 hashFunction2 计算探测步数
		while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
			hashVal += stepSize;
			hashVal %= arraySize; //以指定的步数向后探测
		}
		hashArray[hashVal] = item;
		itemNum++;
	}
	public void extendHashTable() {
		int num = arraySize;
		itemNum = 0; //重新记数，因为下面要把原来的数据转移到新的扩张的数组中
		arraySize *= 2; //数组大小翻倍
		DataItem[] oldHashArray = hashArray;
		hashArray = new DataItem[arraySize];
		for(int i = 0; i < num; i++) {
			insert(oldHashArray[i]);
		}
	}
	public DataItem delete(int key) {
		if(isEmpty()) {
			System.out.println("Hash table is empty!");
			return null;
		}
		int hashVal = hashFunction1(key);
		int stepSize = hashFunction2(key);
		while(hashArray[hashVal] != null) {
			if(hashArray[hashVal].getKey() == key) {
				DataItem temp = hashArray[hashVal];
				hashArray[hashVal] = nonItem;
				itemNum--;
				return temp;
			}
hashVal += stepSize;
			hashVal %= arraySize;
		}
		return null;
	}
	public DataItem find(int key) {
		int hashVal = hashFunction1(key);
		int stepSize = hashFunction2(key);
		while(hashArray[hashVal] != null) {
			if(hashArray[hashVal].getKey() == key) {
				return hashArray[hashVal];
			}
			hashVal += stepSize;
			hashVal %= arraySize;
		}
		return null;
	}
}

    2. 链地址法

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

    public class HashChain {
	private SortedList[] hashArray; //数组中存放链表
	private int arraySize;
	public HashChain(int size) {
		arraySize = size;
		hashArray = new SortedList[arraySize];
		//new 出每个空链表初始化数组
		for(int i = 0; i < arraySize; i++) {
			hashArray[i] = new SortedList();
		}
	}
	public void displayTable() {
		for(int i = 0; i < arraySize; i++) {
			System.out.print(i + ": ");
			hashArray[i].displayList();
		}
	}
	public int hashFunction(int key) {
		return key % arraySize;
	}
	public void insert(LinkNode node) {
		int key = node.getKey();
		int hashVal = hashFunction(key);
		hashArray[hashVal].insert(node); //直接往链表中添加即可
	}
	public LinkNode delete(int key) {
		int hashVal = hashFunction(key);
		LinkNode temp = find(key);
		hashArray[hashVal].delete(key);//从链表中找到要删除的数据项，直接删除
		return temp;
	}
	
	public LinkNode find(int key) {
		int hashVal = hashFunction(key);
		LinkNode node = hashArray[hashVal].find(key);
		return node;
	}
}

    下面是链表类的代码，用的是有序链表：

    public class SortedList {
	private LinkNode first;
	public SortedList() {
		first = null;
	}
	public boolean isEmpty() {
		return (first == null);
	}
	public void insert(LinkNode node) {
		int key = node.getKey();
		LinkNode previous = null;
		LinkNode current = first;
		while(current != null && current.getKey() < key) {
			previous = current;
			current = current.next;
		}
		if(previous == null) {
			first = node;
		}
		else {
			node.next = current;
			previous.next = node;
		}
	}
	public void delete(int key) {
		LinkNode previous = null;
		LinkNode current = first;
		if(isEmpty()) {
			System.out.println("chain is empty!");
			return;
		}
		while(current != null && current.getKey() != key) {
			previous = current;
			current = current.next;
		}
		if(previous == null) {
			first = first.next;
		}
		else {
			previous.next = current.next;
		}
	}
	public LinkNode find(int key) {
		LinkNode 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):");
		LinkNode current = first;
		while(current != null) {
			current.displayLink();
			current = current.next;
		}
		System.out.println("");
	}
}
class LinkNode {
	private int iData;
	public LinkNode next;
	public LinkNode(int data) {
		iData = data;
	}
	public int getKey() {
		return iData;
	}
	public void displayLink() {
		System.out.print(iData + " ");
	}
}

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

    哈希表就分享这么多，小弟我才疏学浅，如有不对之处，请各位大牛指正。后面再继续学习分享，大家也可以关注我的公众号 [程序员私房菜] ，一起学习交流。

    目前尚无回复
    inthashvalhasharraykey
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2801 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 03:02 · PVG 11:02 · LAX 20:02 · JFK 23:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.