目录

哈希表

什么是哈希表

哈希表是由一块地址连续的数组空间构成的,其中每个数组都是一个链表,数组的作用在于快速寻址查找,链表的作用在于快速插入和删除元素,因此,哈希表可以被认为就是链表的数组,下图是一个哈希表的简单示意图:

https://gitee.com/lienhui68/picStore/raw/master/null/20200627105657.png

在存储元素的时候,会用到“散列方法”,它的作用是尽量均衡地将元素分配到数组空间中,避免出现某个数组空间中的链表元素大大超过其它数组空间中链表元素个数的情况。 https://gitee.com/lienhui68/picStore/raw/master/null/20200627105816.png

比较经典的散列函数有“除法散列法”、“平方散列法”、“斐波那契散列法”,这些散列方法在《数据结构》的教材中可以找到,但现在基本都不使用这些了,本文也不再重点讲述这些内容。

当某个链表长度过长的话,查找效率就会急剧下降。因此,一个好的散列方法能确保各个元素均匀地分布到各个数组空间的地址上,避免某个链表过长,这对于哈希表的查找效率是非常重要的。

然而,即使我们拥有了一个好的哈希方法,倘若散列后还是会有很多元素对应同一个数组地址(哈希冲突),则还是会出现单个数组空间中链表元素过多过长的问题,这种情况下怎么解决查询效率慢的问题呢?

一种通用的做法是,将过长的链表转化为二叉查找树、平衡二叉树、红黑树,关于树的数据结构本文不再展开,只需要了解,它们是为了解决单条链表元素过多时查找效率慢的问题,详情可以参考《数据结构》。

hash值的计算

  1. 简单计算就是组成成员的hash值直接相加即可。比如ObjectA有三个属性,propA、propB和propC,最直接的计算方式就是propA.hashcode+propB.hashcode+propC.hashcode。
  2. 但是如果遇到有顺序相关的怎么办?比如String类型是由char数组组成,并且这些数组是有顺序的。如果使用第一种计算方法,则“ABCD”和“BCDA”就会产生同样的hashCode,那么怎么办呢?最直接想到的办法就是加权,不同的index加不同的权值,这个权值的确定最直接的方法就是某个常数值的几次幂。比如为String的计算hash值为K^0*A.hashCode+K^1*B.hashCode+K^2*C.hashCode+K^3*D.hashCode。K的选择也有说法,最好不要是偶数,因为偶数的相乘会造成信息的丢失(乘以2就是左移1位,一旦溢出就会造成信息的丢失,这种计算会造成溢出后的值与某个看似不相关的数值得到的结果是一样的),所以最好是奇数,在这一点上比较推荐使用7,因为7=8-1=2^3-1,这样计算的时候,直接左移几位再进行一次普通的加减法即可(Java中常用的是31(32-1=2^5-1))

参考

Java中的哈希表 浅谈Java中的Hash值