拉链式和线性探测式散列表实现Map

篇我们一起学习了基于数组、链表、二叉树、红黑树来实现Map的操作，本篇我们将会一起来学习基于散列表来实现Map，这种方式对应着java里面的HashMap，这也是使用最多的一种方式

散列表实现Map主要分为了两个步骤:

1. 基于散列函数将被查找键转换为数组的下标
2. 处理散列值冲突的情况，有两种方式来处理冲突：拉链式和线性探测

散列函数

实现散列表的第一步就是需要考虑如何把一个键转换为数组的下标，这时候就需要使用到散列函数，先把键值转换成一个整数然后在使用除留余数法计算出数组的下标。每种类型的键我们都需要一个不同的散列函数。

在java中对于常用的数据类型已经实现了hashCode，我们只需要根据hashCode的值使用除留余数法即可转换成数组的下标

java中的约定：如果两个对象的equals相等，那么hashCode一定相同;如果hashCode相同，equals不一定相同。对于自定义类型的键我们通常需要自定义实现hashCode和equals;默认的hashCode返回的是对象的内存地址，这种散列值不会太好。

下面我来看看Java中常用类型的hashCode计算方式

Integer

由于hashCode需要返回的值就是一个int值，所以Integer的hashCode实现很简单，直接返回当前的value值算一个散列值比较耗时，那么我可以这个计算好的值缓存起来，即使用一个变量把这个值保存起来，在下一次调用时直接返回。Java中的String就是采用的这种方式。

拉链式的散列表

散列函数能够将键值转换成数组的下标;第二步就是需要处理碰撞冲突，也就是需要处理遇到了两个散列值相同的对象应该如何存储。有一种方式是数组中的每一个元素都指向一个链表用来存放散列值相同的对象，这种方式被称为拉链法

拉链法可以使用原始的链表保存键，也可以采用我们之前实现的红黑树来表示，在java8中采用的这两种方式的混合，在节点数超过了8之后变为红黑树。

这里我们就采用简单的链表来实现拉链式散列表，数据结构使用在前几篇中已经实现的LinkedMap，可以参考前面的文章《基于数组或链表实现Map》。

（编辑：泉州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!