`

散列表(Hash table)

阅读更多

散列表Hash table,也叫哈希表),是根据关键码(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

一、基本概念

l散列函数(Hash function):若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。

l冲突:对不同的关键字可能得到同一散列地址,即key1key2,而f(key1)=f(key2),这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词

l均匀散列函数:若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

综上所述,根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象”作为记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址。

二、构造散列函数的方法

l直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=keyH(key) = akey + b,其中ab为常数(这种散列函数叫做自身函数);

l数字分析法:找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址;

l平方取中法: 取关键字平方后的中间几位作为散列地址;

l折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址;

l随机数法: 选择一个随机函数,取关键字的随机函数值为它的散列地址,即h(key)=random(key),其中random为伪随机函数,但要保证函数值是在0m-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());
	}
}
1
4
分享到:
评论

相关推荐

    白话算法之散列表(Hash Table)从理论到实用.doc

    散列表(Hash Table)从理论到实用 散列表(Hash Table)是一种数据结构,它可以实现快速查找、插入和删除操作。下面是关于散列表的理论和实用知识点的总结。 散列表的定义 散列表是一种数据结构,它使用哈希函数...

    在cuda上用gpu实现散列表

    散列表(Hash Table)是一种根据键值(Key-value)对存储数据的数据结构,其核心思想是通过散列函数将键值映射到表的一个位置来访问记录,这加快了查找速度。理想的散列函数应当均匀地分布数据,以减少冲突。 #### ...

    散列表通讯录系统

    首先,我们要了解散列表(Hash Table)的基本概念。散列表是一种通过哈希函数将数据映射到数组中的数据结构,其核心优势在于快速查找和插入操作。它利用了“键-值”对的方式存储数据,通过计算键的哈希值确定元素在...

    c语言或c++课程设计之散列表哈希表

    散列表(Hash Table)是一种数据结构,它通过特定的算法(哈希函数)将数据映射到一个固定大小的数组中,实现快速的查找、插入和删除操作。在C语言或C++中,掌握散列表哈希表的设计是提升编程能力的重要环节。本篇...

    sanliebiao.rar_visual c_散列表_散列表实验

    散列表(Hash Table)是一种常用的数据结构,它通过散列函数将关键字映射到一个固定大小的数组中,实现快速的查找、插入和删除操作。在计算机科学中,尤其是在编程和数据结构的学习中,散列表占有重要地位。Visual ...

    c++,散列表的实现

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...

    sanliebiao.rar_sanliebiao_散列表_散列表c++实现

    散列表(Hash Table)是一种非常重要的数据结构,它在计算机科学和编程中有着广泛的应用,尤其是在数据存储、查找和管理方面。散列表通过散列函数将关键字映射到数组的索引位置,从而实现了快速的插入、删除和查找...

    数据结构散列表编写的电话本及冲突处理源码

    散列表(Hash Table)是一种高效的数据结构,它通过哈希函数将数据映射到一个固定大小的数组中,实现了快速查找、插入和删除操作。在本话题中,我们主要讨论的是一个使用C语言实现的基于散列表的电话本管理系统,它...

    散列表之链接法解决冲突

    散列表(Hash Table)是一种数据结构,用于存储键值对,通过特定的散列函数将键(Key)转化为数组索引,实现快速访问。在实际应用中,由于散列函数的不完美,不同键可能会被映射到相同的索引位置,这种现象称为...

    C++散列表实现电话本存储及查找功能

    在计算机科学中,数据结构是组织和管理大量数据的关键元素,而散列表(Hash Table)是一种高效的数据结构,尤其在快速查找、插入和删除操作上表现出色。在本项目"**C++散列表实现电话本存储及查找功能**"中,我们将...

    设计散列表实现电话号码查找系统

    至于提供的"hash_table"压缩包文件,它可能包含了项目的源代码,包括JavaFX的GUI组件和散列表相关的实现。通过查看和分析这些代码,可以更深入地理解上述概念是如何在实际项目中落地的。 综上所述,设计一个基于散...

    数据结构与算法 - 实验报告5 (散列表构造和查找).pdf

    《实验报告5(散列表构造和查找)》是一篇详细介绍如何使用散列表(Hash Table)结构及其操作,包括构造和查找过程的实验报告。本报告主要聚焦于散列表的基本概念、哈希函数的设计、冲突解决策略以及实际应用中的...

    hashtable hash表 散列表 C源代码

    哈希表(Hash Table),又称为散列表,是一种数据结构,它通过把关键码值映射到表中一个位置来实现查找,使得插入和查找数据的速度都非常快。在C++编程语言中,虽然标准库没有直接提供哈希表的数据结构,但我们可以...

    C语言指导书 数据结构随堂笔记 散列表 排序汇总

    特别是散列表(Hash Table),它通过散列函数将数据映射到一个固定大小的数组中,实现快速查找、插入和删除操作,是很多高效算法的核心。 散列表.doc可能会详细介绍散列函数的设计、冲突解决策略(如开放寻址法、链...

    散列表实现电话号码查找系统

    在IT领域,散列表(Hash Table)是一种高效的数据结构,常用于快速查找和存储数据。在本项目"散列表实现电话号码查找系统"中,我们使用C++编程语言来实现这个系统,它允许用户通过姓名快速查找对应的电话号码。下面...

    基本散列表的线性探查法

    散列表(Hash Table)是一种非常重要的数据结构,它在计算机科学和编程中有着广泛的应用,尤其是在数据存储、查找和关联数组等场景下。线性探查(Linear Probing)是解决散列表冲突的一种方法,本篇文章将深入探讨...

    插队买票——散列表

    标题中的“插队买票——散列表”是一个模拟实际场景的计算机科学问题,它涉及到数据结构中的散列表(Hash Table)及其在解决实际问题中的应用。散列表是一种高效的数据存储和检索结构,它通过特定的散列函数将键...

    kernel_list_and_hash_table.tar.gz_Table_linux内核 list

    "kernel_list_and_hash_table.tar.gz"这个压缩包聚焦于Linux内核中的两种关键数据结构:链表和散列表,以及它们如何被用于实现内核功能。下面我们将详细探讨这两种数据结构及其在Linux内核中的应用。 首先,链表是...

    散列表相关学习代码示例

    散列表(Hash Table)是一种数据结构,它实现了关联数组的抽象数据类型,即可以通过键(Key)来直接访问数组中的元素。散列表的核心思想是通过散列函数将键映射到数组的索引位置,从而实现快速查找。下面将详细阐述...

    【课件】7.5.1散列表的基本概念.pdf

    散列表(Hash Table),也称为哈希表,是一种通过特殊的数据结构实现高效数据查找的数据存储方式。它使用一个被称为哈希函数的映射方法来决定元素存储的位置,并能够快速地访问这些元素。散列表在实际应用中非常广泛...

Global site tag (gtag.js) - Google Analytics