数据结构与算法第六版-HashMap深入

大部分的map都是依靠使用key的地址来定位到value,不过这只是热身运动，我们在设置key的时候限制key是一个integer的数字表示（存储在list中），它的范围在0和list.size-1中，并且list.size的个数要大于map中的entry个数，所以我们会计算 key在list中的位置，查找这表中的数据，

在我们的表述中，我们存储key，value以及这个key在list中的下标，所以大部分的操作，get,put,remove 最坏的执行时间为o(1),

我们扩展这个map框架更加的通用，我们有两个挑战，

第一，我们不希望使用集合的长度，

第二，我们不希望key只能是integer,

这就是一个新的概念 叫做 hash function这种方式指定key的位置，理想状态下key会均衡的分布在list中，但是在测试中，可能会有很多不相同的key，拥有同样的地址，因此，我们会指定一个bucket array 见图，

 

在list中每个位置可能会存储多个entry,如果他们在hash function 之后index相同，

Hash Functions
hashFunctions 会定位map中的每一个key,在list中的位置，然后我们会存储这个entry在list中，好比说

map.put("a",12); 我们会根据a的hash functions 找到这个entry在list中的位置

如果两个或者更多的key拥有相同的hash code，但是他们是不同的entry,他们会定位到相同的index中，这种情况我们叫”碰撞“

一个好的hash function会减少碰撞的可能性，

通常来讲，我们计算hashcode的，通常分为两个步骤，一个是 hash functiuon 第二步则是，compression function（解压操作），map中的hashcode在集合中的范围是（0，size-1）