散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
一、基本概念
l散列函数(Hash function):若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。
l冲突:对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。
l均匀散列函数:若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。
综上所述,根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象”作为记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址。
二、构造散列函数的方法
l直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b,其中a和b为常数(这种散列函数叫做自身函数);
l数字分析法:找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址;
l平方取中法: 取关键字平方后的中间几位作为散列地址;
l折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址;
l随机数法: 选择一个随机函数,取关键字的随机函数值为它的散列地址,即h(key)=random(key),其中random为伪随机函数,但要保证函数值是在0到m-1之间;
l除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。
三、处理冲突的方法
l开放寻址法:Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列三种取法:
1.di=1,2,3,…, m-1,称线性探测再散列;
2.di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;
3.di=伪随机数序列,称伪随机探测再散列。
l再散列法:Hi=RHi(key), i=1,2,…,k. RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间;
l链地址法(拉链法):将所有关键字为同义词的记录存储在同一线性链表中;
l建立一个公共溢出区。
四、查找性能分析
在哈希表上进行查找的过程和哈希造表的过程是一致的。一些关键码可通过散列函数转换的地址直接找到,而另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。查找过程中,关键码的比较次数,取决于产生冲突的多少,影响产生冲突多少有以下三个因素:
1. 散列函数是否均匀;
2. 处理冲突的方法;
3. 散列表的装填因子α= 填入表中的元素个数 / 散列表的长度。
α是散列表装满程度的标志因子。散列表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。
五、散列表java实现(MyHashtable)
下面是散列表的一个简单实现,采用开放寻址法线性探测解决冲突,参考《数据结构Java语言描》,Micheal Main著。
public class MyHashtable {
private int manyItems;//表中元素个数
private Object[] keys;
private Object[] data;
private boolean[] hasBeenUsed;//若索引i处存在元素,则hasBeenUsed[i]为ture,否则为false
public MyHashtable(int capacity) {
if(capacity <= 0)
throw new IllegalArgumentException("capacity is negative");
keys = new Object[capacity];
data = new Object[capacity];
hasBeenUsed = new boolean[capacity];
}
//hash函数
private int hash(Object key) {
return Math.abs(key.hashCode()%data.length);
}
//当前索引发生冲突,找下一索引
private int nextIndex(int i) {
if(i + 1 == data.length) {
return 0;
} else {
return i + 1;
}
}
//如果在表中找到指定的关键字,返回值为关键字的索引,否则返回-1
private int findIndex(Object key) {
int count = 0;
int i = hash(key);
while((count < data.length) && hasBeenUsed[i]) {
if(key.equals(keys[i])) {
return i;
} else {
count++;
i = nextIndex(i);
}
}
return -1;
}
public Object get(Object key) {
int index = findIndex(key);
if(index == -1) {
return null;
} else {
return data[index];
}
}
public Object put(Object key, Object element) {
int index = findIndex(key);
Object answer;
if(index != -1) {
answer = data[index];
data[index] = element;
return answer;
} else if(manyItems < data.length) {
index = hash(key);
while(keys[index] != null) {
index = nextIndex(index);
}
keys[index] = key;
data[index] = element;
hasBeenUsed[index] = true;
manyItems++;
return null;
} else {
throw new IllegalStateException("Hashtable is full!");
}
}
public Object remove(Object key) {
int index = findIndex(key);
Object answer = null;
if(index != -1) {
answer = data[index];
data[index] = null;
keys[index] = null;
manyItems--;
}
return answer;
}
public boolean contains (Object key) {
return (findIndex(key) != -1);
}
public static void main(String[] args) {
MyHashtable table = new MyHashtable(100);
table.put(1, "china");
table.put(2, "美国");
System.out.println(table.get(2).toString());
}
}
分享到:
相关推荐
散列表(Hash Table)从理论到实用 散列表(Hash Table)是一种数据结构,它可以实现快速查找、插入和删除操作。下面是关于散列表的理论和实用知识点的总结。 散列表的定义 散列表是一种数据结构,它使用哈希函数...
散列表(Hash Table)是一种根据键值(Key-value)对存储数据的数据结构,其核心思想是通过散列函数将键值映射到表的一个位置来访问记录,这加快了查找速度。理想的散列函数应当均匀地分布数据,以减少冲突。 #### ...
首先,我们要了解散列表(Hash Table)的基本概念。散列表是一种通过哈希函数将数据映射到数组中的数据结构,其核心优势在于快速查找和插入操作。它利用了“键-值”对的方式存储数据,通过计算键的哈希值确定元素在...
散列表(Hash Table)是一种数据结构,它通过特定的算法(哈希函数)将数据映射到一个固定大小的数组中,实现快速的查找、插入和删除操作。在C语言或C++中,掌握散列表哈希表的设计是提升编程能力的重要环节。本篇...
散列表(Hash Table)是一种常用的数据结构,它通过散列函数将关键字映射到一个固定大小的数组中,实现快速的查找、插入和删除操作。在计算机科学中,尤其是在编程和数据结构的学习中,散列表占有重要地位。Visual ...
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
散列表(Hash Table)是一种非常重要的数据结构,它在计算机科学和编程中有着广泛的应用,尤其是在数据存储、查找和管理方面。散列表通过散列函数将关键字映射到数组的索引位置,从而实现了快速的插入、删除和查找...
散列表(Hash Table)是一种高效的数据结构,它通过哈希函数将数据映射到一个固定大小的数组中,实现了快速查找、插入和删除操作。在本话题中,我们主要讨论的是一个使用C语言实现的基于散列表的电话本管理系统,它...
散列表(Hash Table)是一种数据结构,用于存储键值对,通过特定的散列函数将键(Key)转化为数组索引,实现快速访问。在实际应用中,由于散列函数的不完美,不同键可能会被映射到相同的索引位置,这种现象称为...
在计算机科学中,数据结构是组织和管理大量数据的关键元素,而散列表(Hash Table)是一种高效的数据结构,尤其在快速查找、插入和删除操作上表现出色。在本项目"**C++散列表实现电话本存储及查找功能**"中,我们将...
至于提供的"hash_table"压缩包文件,它可能包含了项目的源代码,包括JavaFX的GUI组件和散列表相关的实现。通过查看和分析这些代码,可以更深入地理解上述概念是如何在实际项目中落地的。 综上所述,设计一个基于散...
《实验报告5(散列表构造和查找)》是一篇详细介绍如何使用散列表(Hash Table)结构及其操作,包括构造和查找过程的实验报告。本报告主要聚焦于散列表的基本概念、哈希函数的设计、冲突解决策略以及实际应用中的...
哈希表(Hash Table),又称为散列表,是一种数据结构,它通过把关键码值映射到表中一个位置来实现查找,使得插入和查找数据的速度都非常快。在C++编程语言中,虽然标准库没有直接提供哈希表的数据结构,但我们可以...
特别是散列表(Hash Table),它通过散列函数将数据映射到一个固定大小的数组中,实现快速查找、插入和删除操作,是很多高效算法的核心。 散列表.doc可能会详细介绍散列函数的设计、冲突解决策略(如开放寻址法、链...
在IT领域,散列表(Hash Table)是一种高效的数据结构,常用于快速查找和存储数据。在本项目"散列表实现电话号码查找系统"中,我们使用C++编程语言来实现这个系统,它允许用户通过姓名快速查找对应的电话号码。下面...
散列表(Hash Table)是一种非常重要的数据结构,它在计算机科学和编程中有着广泛的应用,尤其是在数据存储、查找和关联数组等场景下。线性探查(Linear Probing)是解决散列表冲突的一种方法,本篇文章将深入探讨...
标题中的“插队买票——散列表”是一个模拟实际场景的计算机科学问题,它涉及到数据结构中的散列表(Hash Table)及其在解决实际问题中的应用。散列表是一种高效的数据存储和检索结构,它通过特定的散列函数将键...
"kernel_list_and_hash_table.tar.gz"这个压缩包聚焦于Linux内核中的两种关键数据结构:链表和散列表,以及它们如何被用于实现内核功能。下面我们将详细探讨这两种数据结构及其在Linux内核中的应用。 首先,链表是...
散列表(Hash Table)是一种数据结构,它实现了关联数组的抽象数据类型,即可以通过键(Key)来直接访问数组中的元素。散列表的核心思想是通过散列函数将键映射到数组的索引位置,从而实现快速查找。下面将详细阐述...
散列表(Hash Table),也称为哈希表,是一种通过特殊的数据结构实现高效数据查找的数据存储方式。它使用一个被称为哈希函数的映射方法来决定元素存储的位置,并能够快速地访问这些元素。散列表在实际应用中非常广泛...