博客

HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对(Entry)分散存储在一个数组中，数组就是HashMap的主干。

HashMap数组的每一个元素初始值都为空。(NULL）

哈希表常用方法有Get和Put

Put方法的原理，

1.先由哈希表通过哈希函数来确定Key-Value的插入位置，比如为数组a的，a[2]。

2.但是无论再优秀的哈希函数，总会有可能出现不同的值占用一个位置

例如，a[2]=”hello”,与此同时，”hi”通过哈希函数寻址，也找到了a[2]这个位置，此时会出现冲突。

3.解决冲突的方法是通过引入链表来解决，例如，a[2]=”hello”;在a[2]的位置设置next指针来连接各个键值对对象(Entry对象)，a[2]=”hello”->a[2]=”hi”

4.实际上是”头插法”，新来的Entry对象插在就对象头上，因为设计者会觉得新对象更可能被人们使用

Get方法的原理，

1.每一次都要使用Key(键)通过哈希函数进行映射来寻找Value(值),来取得索引(index)

2.再次以a[2]为例子，在a[2]中寻找”hello”，由于a[2]->”hi”，a[2]->”hello”(头插法),从上往下查找”hello”是所要取的值

这就是哈希表的原理，包括键值对(Entry),通过哈希函数取值、取索引，Get方法和Put方法