Java数据结构之散列表(动力节点Java学院整理)

基本概念

散列表(Hash table,也叫哈希表),是根据关键字(key value)而直接进行访问的数据结构。

说的具体点就是它通过吧key值映射到表中的一个位置来访问记录,从而加快查找的速度。

实现key值映射的函数就叫做散列函数

存放记录的数组就就叫做散列表

实现散列表的过程通常就称为散列(hashing),也就是常说的hash

散列

这里的散列的概念不仅限于数据结构了,在计算机科学领域中,散列-哈希是一种对信息的处理方法,通过某种特定的函数/算法(散列函数/hash()方法)将要检索的项与用来检索的索引--( 散列值)关联起来,生成一种便于搜索的数据结构--散列表。如今,由于散列算法所计算的散列值 具有不可逆(无法逆向演算会原来的数值)的性质,因此散列算法广泛的运用于加密技术。

散列的运用:

1、加密散列,在信息安全领域使用

2、散列表,一种使用散列函数将键名和键值关联起来的数据结构

3、关联数组,一种常常使用散列表来实现的数据结构

4、几何散列,寻找相同或相似的几何形状的一种有效方法

散列函数

通过上面可以知道,散列技术的实现是基于散列函数的。这里对散列函数进行一个较深入的理解。前面就知道了散列函数--哈希函数就是完成key值与位置的映射。一般说来key以字符 串的形式居多,位置也就是一个数值。可以看出散列函数就像是实现信息的压缩,把消息字符 串压缩成数值摘要,是数据量变小,格式得以固定下来。
散列函数的工作原理图:

不过需要注意的是key值和经过散列函数处理之后的散列值并不是唯一对应的,这就造成了不同的key值具有相同的索引位置,这种现象叫做散列碰撞、也称其为哈希冲突。对于hash冲突的解决办法,将在后面予以总结。至于散列函数的具体实现,有很多加密技术都有十分nice的实现,这里我们看看Java中HashMap的hash()方法实现就可以了。HashMap采用的是内部哈希技术实现的,其中hash()方法就是散列函数,完成key值到数组索引位置的映射。

 /**
  * Retrieve object hash code and applies a supplemental hash function to the
  * result hash, which defends against poor quality hash functions. This is
  * critical because HashMap uses power-of-two length hash tables, that
  * otherwise encounter collisions for hashCodes that do not differ
  * in lower bits. Note: Null keys always map to hash 0, thus index 0.
  */
 final int hash(Object k) {
  int h = 0;
  if (useAltHashing) {
   if (k instanceof String) {
    return sun.misc.Hashing.stringHash32((String) k);
   }
   h = hashSeed;
  }
  h ^= k.hashCode();
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
 } 

上述代码就是HashMap中散列函数的具体实现。JDK1.7这里笔者对常用的散列算法做一个展示:

散列表

在理解了上述散列\散列函数的概念之后我们正式的进入到散列表的学习.一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表(即建立人名 x 到首字母 F(x) 的一个函数关系),在首字母为 W 的表中查找“王”姓的电话号码,显然比直接查找就要快得多。这里使用人名作为关键字,“取首字母”是这个例子中散列函数的函数法则 F(),存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

散列函数的构造

对于散列表这种数据结构来说,其散列函数的构造是十分关键的,散列函数实现了key的映射,并且访问记录可以更快的被定位。一般来说散列函数的构造基于两个标准:简单、均匀简单指散列算法简单快捷,散列值生成简单。均匀指对于key值集合中的任一关键字,散列函数能够以均与的概率映射到数组的任一一个索引位置上,这样能够减少散列碰撞。
散列函数构造方法:

1、直接地址法:

直接取key值或者key值的某个线性函数值作为散列地址。即hash(k)=k或者hash(k)=a*k+b。

Tips: 简单的思考一下这种方式就可以知道,这种方式基本不会存在哈希冲突,不过事先我们应该知道key集合的大小,而且使用线性函数值作为散列地址的话,很大程度上造成了空间的浪费。hash(k)=k这种方式更加的鸡肋没必要,以这种方式散列还不如直接数组索引。

2、数字分析法:

所谓的数字分析法就是假设关键字key是以r为基的数,并且hash表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成hash地址。

Tips:这种方式极度不灵活,限制太多。

3、平方取中法:

先通过求关键字的平方值扩大相近数的差别,然后根据表长度取中间的几位数作为散列函数值。

Tips:这种方式中间的几位数都和关键字的没一位都有关,产生的散列地址较为的均匀。

4、折叠法:

将关键字分割成相同的几位数(最后一位可不同),然后去这几部分的叠加和。折叠法一般是和除留余法一起使用的。

5、除留余法:

取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 hash(k)= k mod p, p < m。不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对 p 的选择很重要,一般取素数或 m ,若 p 选择不好,容易产生碰撞。

6、随机法:

h(key)=random(key)    其中random为伪随机函数,但要保证函数值是在0到m-1之间。总结:在上述的方法中,3、4、5三种方法的结合使用方式较好,在JDK以前的版本就是使用的方法5。

哈希冲突

通过上面的学习中,我们知道散列函数得到的key -  索引位置 并不是唯一对应的,可能造成不同的key值对应相同的索引位置。这是我们应该解决的问题。实际的解决方法一般如下:

1、分离连接法:

首先看看分离连接法,说白了这种方式就是链表数组的方式,将散列到同一个值得所有元素保存在一个表中,产生相同的一个值在散列表中使用链表的形式存储。哈希冲突的位置就是链表的开始位置。在JKD中HashMap就是这种方式解决哈希冲突的!

HashMap中冲突处理代码如下

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
   Object k;
   if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
   }
  } 

2、开放地址法

分离连接法的缺点在于使用了链表,由于给新的单元分配地址耗费时间,造成算法速度较慢,解决的方法就是开放地址法,在开放地址法中较为常用的有两种:线性探测法、平方探测法。 
开放地址法:

hash_i=(hash(key) + d(i)) mod m, i=1,2...k\,(k < m-1),其中hash(key)为散列函数,m为散列表长,d(i)为增量序列,i为已发生碰撞的次数。增量序列可有下列取法:

d(i)=1,2,3...(m-1) 称为 线性探测;即 d(i)=i ,或者为其他线性函数。相当于逐个探测存放地址的表,直到查找到一个空单元,把散列地址存放在该空单元。d(i)=1^2,  2^2,3^2... k^2 (k < m/2) 称为 平方探测。相对线性探测,相当于发生碰撞时探测间隔 d(i)=i^2 个单元的位置是否为空,如果为空,将地址存放进去。d(i)=伪随机数序列,称为 伪随机探测。

线性探测法

下面笔者将以一个实例演示线性探测的过程,进而分析线性探测的特点,引出平方探测关键字为{89,18,49,58,69}插入到一个散列表中的情况。此时线性探测的方法是取d(i)=i。并假定取关键字除以 10 的余数为散列函数法则。

1、开始时hash(89)=9无冲突,直接插入;

2、hash(18)=8无冲突,直接插入;

3、hash(49)=9冲突了,开放地址,将49放入下一个空闲地址0

4、hash(58) =8冲突了,开放地址,将58放入9冲突 ,放入0冲突、放入1

5、hash(69) =9冲突,开放地址,将69放入0冲突,放入1冲突,放入2

Tips:思考其缺点!

线性探测的方式十分简单,明白,每次插入总是能够找到一个地址,但是慢慢会形成一个区块,其结果称为一次聚集。任何关键字需探测越来越多的次数才能解决冲突,且完成之后由简介的增大了区块。当填装因子>0.5时,这种方式就不是个好的方法了!

平方探测法:

使用平方探测法可以解决线性探测的一次聚集问题。一般选择d(i)=i^2.。至于其具体的步骤读者可以按照上面的实例自行的模拟一下。这种方式会出现二次聚集的情况:散列到同一位置的哪些元素将探测相同的备选单元。

3、双散列、再散列

对于双散列和再散列的方式笔者这里就不在多提了。读者可以查阅下相关的资料。总结:对于散列表的实现新手不必太过在意,关键在于理解散列相关的概念。了解并掌握散列函数的作用及一般的实现方式。了解一般hash冲突和常用解决办法。

以上所述是小编给大家介绍的Java数据结构之散列表(动力节点Java学院整理),希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!

(0)

相关推荐

  • Java常见基本数据结构概览

    Java数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科.在Java数据结构中最常用的类型无外乎以下几种: Map接口 请注意,Map没有继承Collection接口,Map提供key到value的映射.一个Map中不能包含相同的key,每个key只能映射一个value. Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射. List接口 List是有序的Collection,用户能

  • java数据结构与算法之快速排序详解

    本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • Java数据结构之图(动力节点Java学院整理)

    1,摘要: 本文章主要讲解学习如何使用JAVA语言以邻接表的方式实现了数据结构---图(Graph).从数据的表示方法来说,有二种表示图的方式:一种是邻接矩阵,其实是一个二维数组:一种是邻接表,其实是一个顶点表,每个顶点又拥有一个边列表.下图是图的邻接表表示. 从图中可以看出,图的实现需要能够表示顶点表,能够表示边表.邻接表指是的哪部分呢?每个顶点都有一个邻接表,一个指定顶点的邻接表中,起始顶点表示边的起点,其他顶点表示边的终点.这样,就可以用邻接表来实现边的表示了.如顶点V0的邻接表如下: 与

  • 浅析Java 数据结构常用接口与类

    Java工具包提供了强大的数据结构.在Java中的数据结构主要包括以下几种接口和类: 枚举(Enumeration) 位集合(BitSet) 向量(Vector) 栈(Stack) 字典(Dictionary) 哈希表(Hashtable) 属性(Properties) 以上这些类是传统遗留的,在Java2中引入了一种新的框架-集合框架(Collection),我们后面再讨论. 枚举(Enumeration) 枚举(Enumeration)接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里

  • java数据结构与算法之插入排序详解

    本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

  • java数据结构与算法之希尔排序详解

    本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一

  • Java数据结构之散列表(动力节点Java学院整理)

    基本概念 散列表(Hash table,也叫哈希表),是根据关键字(key value)而直接进行访问的数据结构. 说的具体点就是它通过吧key值映射到表中的一个位置来访问记录,从而加快查找的速度. 实现key值映射的函数就叫做散列函数 存放记录的数组就就叫做散列表 实现散列表的过程通常就称为散列(hashing),也就是常说的hash 散列 这里的散列的概念不仅限于数据结构了,在计算机科学领域中,散列-哈希是一种对信息的处理方法,通过某种特定的函数/算法(散列函数/hash()方法)将要检索的

  • Java数据结构之散列表详解

    目录 介绍 1 散列表概述 1.1 散列表概述 1.2 散列冲突(hash collision) 2 散列函数的选择 2.1 散列函数的要求 2.2 散列函数构造方法 3 散列冲突的解决 3.1 分离链接法 3.2 开放定址法 3.3 再散列法 4 散列表的简单实现 4.1 测试 介绍 本文详细介绍了散列表的概念.散列函数的选择.散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现. 数组的特点是寻址容易,插入和删除困难:而链表的特点是寻址困难,插入和删除容易.而对于tree结构,它们

  • Java 中HashCode作用_动力节点Java学院整理

    第1 部分 hashCode的作用 Java集合中有两类,一类是List,一类是Set他们之间的区别就在于List集合中的元素师有序的,且可以重复,而Set集合中元素是无序不可重复的.对于List好处理,但是对于Set而言我们要如何来保证元素不重复呢?通过迭代来equals()是否相等.数据量小还可以接受,当我们的数据量大的时候效率可想而知(当然我们可以利用算法进行优化).比如我们向HashSet插入1000数据,难道我们真的要迭代1000次,调用1000次equals()方法吗?hashCod

  • Java成员变量与局部变量(动力节点Java学院整理)

    成员变量 我们来研究一个事物: 属性:外在特征:例如人的身高,体重 行为:能够做什么:例如人有说话,打球等行为. 而在Java语言中,最基本的单位是类,类就是用来体现事物的. 用类class来描述事物也是如此: 属性:对应类中的成员变量    行为:对应类中的成员函数 定义类其实就是在定义类中的成员(成员变量和成员函数) 拓展:类是一个抽象的概念,而对象就是类的具体的存在,体现.例如:生活中的汽车,可以看做一个类,我们称之为汽车类,每一台车都有颜色和轮胎数(可以定义为属性,即成员变量),每一台车

  • Java数组的特性_动力节点Java学院整理

    Java中的数组是对象吗? Java和C++都是面向对象的语言.在使用这些语言的时候,我们可以直接使用标准的类库,也可以使用组合和继承等面向对象的特性构建自己的类,并且根据自己构建的类创建对象.那么,我们是不是应该考虑这样一个问题:在面向对象的语言中,数组是对象吗? 要判断数组是不是对象,那么首先明确什么是对象,也就是对象的定义.在较高的层面上,对象是根据某个类创建出来的一个实例,表示某类事物中一个具体的个体.对象具有各种属性,并且具有一些特定的行为.而在较低的层面上,站在计算机的角度,对象就是

  • Java构造方法实例详解(动力节点java学院整理)

    构造函数是一种特殊的函数.其主要功能是用来在创建对象时初始化对象, 即为v对象成员变量赋初始值,总与new运算符一起使用在创建对象的语句中.构造函数与类名相同,可重载多个不同的构造函数.在JAVA语言中,构造函数与C++语言中的构造函数相同,JAVA语言中普遍称之为构造方法. 使用构造器时需要记住: 1.构造器必须与类同名(如果一个源文件中有多个类,那么构造器必须与公共类同名) 2.每个类可以有一个以上的构造器 3.构造器可以有0个.1个或1个以上的参数 4.构造器没有返回值 5.构造器总是伴随

  • Java BigDecimal详解_动力节点Java学院整理

    1.引言 借用<Effactive Java>这本书中的话,float和double类型的主要设计目标是为了科学计算和工程计算.他们执行二进制浮点运算,这是为了在广域数值范围上提供较为精确的快速近似计算而精心设计的.然而,它们没有提供完全精确的结果,所以不应该被用于要求精确结果的场合.但是,商业计算往往要求结果精确,例如银行存款数额,这时候BigDecimal就派上大用场啦. 2.BigDecimal简介 BigDecimal 由任意精度的整数非标度值 和32 位的整数标度 (scale) 组

  • Java接口的作用_动力节点Java学院整理

    1. 接口是一种规范 很好,你已经知道接口是一种规范了! 下面这张图是我们生活中遇到的接口:电源插座接口. 2. 为什么需要规范呢? 因为有了接口规范: • 任何电器只有有符合规范的插头,就可以获得电力 • 任何厂家(西门子插座,TCL插座,公牛插座...)按照规范进行制作,就能进行供电 每个厂家插座的生产技术.工艺都不一样,因为接口的implementation可以不一样,但是并不影响电器的正常工作.插座的内部实现对于电器来说是完全屏蔽的. 对于软件开发同样也是类似的: • 按照接口规范进行方

  • Java中StringBuffer和StringBuilder_动力节点Java学院整理

    下面先给大家介绍下String.StringBuffer.StringBuilder区别,具体详情如下所示: StringBuffer.StringBuilder和String一样,也用来代表字符串.String类是不可变类,任何对String的改变都 会引发新的String对象的生成:StringBuffer则是可变类,任何对它所指代的字符串的改变都不会产生新的对象.既然可变和不可变都有了,为何还有一个StringBuilder呢?相信初期的你,在进行append时,一般都会选择StringB

  • Java项目开发命名规范(动力节点Java学院整理)

    最好使用英文,不要用汉语拼音 1:包(package):用于将完成不同功能的类分门别类,放在不同的目录(包)下,包的命名规则:将公司域名反转作为包名.比如www.bjpowernode.com 对于包名:每个字母都需要小写.比如:com. bjpowernode.test;该包下的Test类的全名是:com. bjpowernode.Test.java .如果定义类的时候没有使用package,那么java就认为我们所定义的类位于默认包里面(default package). 2:类:首字母大写

随机推荐

其他