数据结构是哈希表(hashTable)

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

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

1.开放地址法

线性探测法

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

public class HashTable {
	
	private DataItem[] hashArray; // DateItem类是数据项,封装数据信息
	private int arraySize=10;
	private int itemNum; // 数组中目前存储了多少项
	private DataItem nonItem; // 用于删除项的

	public HashTable() {
		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. 不能输出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 HashTableDouble {
	private DataItem[] hashArray;
	private int arraySize;
	private int itemNum;
	private DataItem nonItem;

	public HashTableDouble() {
		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;
	}
}

class DataItem {
	private int iData;

	public DataItem(int data) {
		iData = data;
	}

	public int getKey() {
		return iData;
	}
}

2.链地址法

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

public class HashTableDouble {
	private SortedList[] hashArray; // 数组中存放链表
	private int arraySize;

	public HashTableDouble(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;
	}
}

这里用的链表是有序链表LinkNode

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)的时间级。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Golang语言之异常处理

在编写Go语言代码的时候,我们应该习惯使用error类型值来表明非正常的状态。作为惯用法,在Go语言标准库代码包中的很多函数和方法也会以返回error类型值来表...

358130
来自专栏申龙斌的程序人生

零基础学编程006:赋值语句

继续上次的一道练习题: 如何用Python打印这篇看上去很枯燥的《复利数据表》: (1+0.01) ^ 1 = 1.01 (1+0.01) ^ 2 = 1.0...

29450
来自专栏iOS技术杂谈

Java8 Lambda表达式与Stream API (二): Stream API的使用你要知道的Java8 匿名内部类、函数式接口、lambda表达式与Stream API都在这里

你要知道的Java8 匿名内部类、函数式接口、lambda表达式与Stream API都在这里 转载请注明出处 https://cloud.tencent.co...

54760
来自专栏码云1024

python简明笔记

通过 for 语句我们可以使用 for 循环。Python 里的 for 循环与 C 语言中的不同。这里的 for 循环遍历任何序列(比如列表和字符串)中的每一...

62090
来自专栏Google Dart

Dart语言指南(二) 顶

Dart是一种面向对象的语言 包含类和基于 mixin 的继承两部分。每个对象是一个类的实例, 并且 Object.是所有类的父类。 基于 mixin 的继承指...

27610
来自专栏偏前端工程师的驿站

意译:自调用函数表达式

一、写在前面   本文将一如既往地遵循从自身理解出发,而非100%按原文逐句翻译的方式进行“伪翻译”,若有谬误请各位指正,谢谢!! 二、介绍   IIFE(th...

21480
来自专栏数据之美

Python FAQ(常见问题解答)(1)

声明:转载需署名出处,严禁用于商业用途! 1、python的帮助: help(str) 可以查看str字符类的帮助信息。 2、python没有括号来表明...

29180
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-11总结Eclipse使用,API,Object类

1:Eclipse的概述使用(掌握) 1:Eclipse的安装 2:用Eclipse写一个HelloWorld案例,最终在控制台输出你的名字 A:创建项目 ...

36560
来自专栏JAVA高级架构

Java面试题合集

1.抽象类与接口的区别是什么? 一个类可以实现多个接口,但是只能继承以及抽象类。类如果要实现一个接口,它必须要实现接口声明的所有方法。但是,类可以不实现抽象类声...

381100
来自专栏JavaEdge

Java语法糖1 泛型与类型擦除

38770

扫码关注云+社区

领取腾讯云代金券