Video在线视频

这一节我们来介绍一下

哈希映射与哈希表

哈希映射实际上

是基哈希表来对Map接口的一种实现

它提供了所有可选的映射操作

并允许使用空值和空键

那哈希映射的话

它本身是非线程安全的

关于非线程安全的这个定义

在前面两节都已经介绍过了

那哈希映射的话

它不保证映射的顺序

特别是它不保证这个顺序

是保持恒久不变的

那哈希映射数据结构呢

实际上是分两级

那第一级的话

实际上它是一个数组

那这个数组往下的话

实际上是保存了

很多映射的这些值

而我们看一下

它这个通过代码描述的

它的数据结构transient Entry table

实际上我们说

它第一级就是一个数组

数组那个是

我们这给它取个名字叫table

它当中的每一个元素

它的类型是Entry

那么我们看它每一个元素Entry

又是长的什么样的呢

static class Entry K V

implements Map点Entry K V

然后我们看一下里面

final K 是key V value

然后Entry K V next

也就是说它像是一个链表

它指明说我往下

下一个元素下一个结点这个Entry是谁

final int hash

所以说这个总结下来

HashMap底层就是一个它数组结构

数组中的每一项又是一个链表

先建一个的时候

就会初始化这么一个数组

Entry就是数组中的元素

那么每个Map Entry

其实就是一个K value对

它只有一个向下的指针

来指示我们下个元素

这就构成了链表

我们来看一下这个HashMap

怎么去往里添加

这么一个它的元素

public V put K value

也就是说你怎么

去往里添加一个K value

那首先它会判断说

K是不是等于空

这个如果是空的话是直接去返回

调用putForNullKey

这个方法并返回

如果不是空的话

那我们要看一下

这个K的它的哈希值

也就是int hash

等于hash key点hash Code

通过这个哈希值后就知道

它在我们这个数组结构当中

它的下标是多少

那我们就找到

相应的这个数组元素

那这个数组元素呢

其实它就是一个

Entry类型的这个对象

那我们看下面

forEntry K V e等于table i

table i就是我们通过这个哈希值

这个作为下标

找到我们数组当中的这个Entry

紧接着我们用

e不等于空e等于e点next

实际上是通过这个链表

去找到它的一个下一个这个元素

那下一个元素

我们最主要是比较说

这个K是不是这个一样

那么我们找到这个K了以后呢

就把相应的value值添加这个进去

那这个里面都写了很多这个代码

来怎么去保存原有的值

然后把我们新的value值

放到我们e的value这当中

最后我们

对这个修改的技术进行加一

然后再把整个这个Entry add进去

然后返回空

这是这个我们的put方法

那在这个过程当中

我们调用了Hash这个方法

那Hash方法

这是它里面内部一种实现

这个Hash的函数有多种实现方式

这里只是展现了它一种可能性

那再往下这个方法是add Entry

add Entry实际上就是说

我把我要想加进的K value

加到我这个HashMap

这个结构当中的

那个链表的那个里面

通过这个方法把它插入进去

那最后这个一个方法是查询

根据哈希值来查询

相对应的这个数组

这个table的位置

static int indexFor

int h int length

直接返回就是h以上的length减一

那这个例子里面

我们可以看到这个HashMap

底层数组的长度它总是2的N次方

这就是为了保证数组的使用率最高

尽可能的减少这个碰撞现象的产生

当HashMap中的元素越来越多的时候

这个哈希冲撞的冲突的

可能性也就越来越高

因为数组的长度是固定的

那为了提高这查询的效率

就要对这个HashMap的数组进行扩容

容量变为原来的两倍

那这时候呢

原数组当中的数据必须重新计算

它在新数组当中的位置

并且放进去

那这个过程呢就非常耗时

当HashMap中的元素个数

超过数组大小的这个

我们取个名字叫（lot fat）

就会进行数组的扩容

那这个（lot fat）的默认值为0.75

那这个是一个非常消耗性能的操作

所以如果我们已经预知

这个HashMap当中元素的个数

那么预测元素的个数

就能够有效的提高HashMap的性能

所以这也是一个HashMap

它的一个独特的地方

那么我们再看一下

HashMap的一个反向过程

因为刚才我们是PUT

就是往里面增加K value

那现在话你应该还要可以

把它取出来 对不对

我要从我的HashMap结构当中

取出一个K value的话

我怎么取

public V get Object key

也就是说我给它一个key

我要取出value

那我们首先要根据key

来找到它所对应的我们HashMap中

第一节数组结构中的它的这个下标

然后根据它的下标得到一个链表

那再通过这个链表当中

依次来去匹配所对应的key

然后同它对应的key当中

去得到它的value

然后并且进行返回

这个就是

我们这个方法的主要的原理

我们还有另外一类

叫HashTable叫哈希表

那刚才我们介绍是哈希映射HashMap

那这两类呢

它采用相同的存储机制

二者的实现基本是一致的

那HashTable

它不允许有空值的存在

不能说我的key它是一个null

这个不行

然后HashTable它是线程安全的

也就是说它内部的很多方法

它都已经实现了用synchronized

来实现了这个线程的安全控制

然后HashTable的迭代器具有强一致性

那这一节内容我们就介绍到这里