HashMap、HashSet、ArrayList实现机制

1.HashMap实现机制：

我们首先看一下什么是hash算法（摘自百度知道）：

这个问题有点难度，不是很好说清楚。 我来做一个比喻吧。 
我们有很多的小猪，每个的体重都不一样，假设体重分布比较平均(我们考虑到公斤级别)，我们按照体重来分,划分成100个小猪圈。 
然后把每个小猪，按照体重赶进各自的猪圈里，记录档案。 好了，如果我们要找某个小猪怎么办呢？我们需要每个猪圈，每个小猪的比对吗？ 
当然不需要了。 我们先看看要找的这个小猪的体重，然后就找到了对应的猪圈了。 
在这个猪圈里的小猪的数量就相对很少了。 
我们在这个猪圈里就可以相对快的找到我们要找到的那个小猪了。 对应于hash算法。 
就是按照hashcode分配不同的猪圈，将hashcode相同的猪放到一个猪圈里。 
查找的时候，先找到hashcode对应的猪圈，然后在逐个比较里面的小猪。 所以问题的关键就是建造多少个猪圈比较合适。 如果每个小猪的体重全部不同（考虑到毫克级别)，每个都建一个猪圈，那么我们可以最快速度的找到这头猪。缺点就是，建造那么多猪圈的费用有点太高了。 如果我们按照10公斤级别进行划分，那么建造的猪圈只有几个吧，那么每个圈里的小猪就很多了。我们虽然可以很快的找到猪圈，但从这个猪圈里逐个确定那头小猪也是很累的。 所以，好的hashcode，可以根据实际情况，根据具体的需求，在时间成本(更多的猪圈，更快的速度)和空间本(更少的猪圈，更低的空间需求)之间平衡。      

了解了什么是hashmap之后，我们看一下java是怎么实现的：

java是通过组数+链实现hashMap的（如果不懂，通过调试查看定义的hashMap里面的值可以清楚的看懂）

请看下面是hashMap定义的常量

static final int DEFAULT_INITIAL_CAPACITY = 16;//定义初始化有几个容器（猪圈）

static final float DEFAULT_LOAD_FACTOR = 0.75f;//定义初始化加载因子（意思是当hashMap的个数大于16*0.75的时候，hashMap要再增加容器）

transient Entry[] table;//这个是数组，就是容器（猪圈数组）

存储：

当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。（所以整个过程跟value没多大关系）

2.HashSet的实现机制：

跟hashMap一样，都是调用hashMap的方法

3.ArrayList的实现机制

其实质就是对数组的操作

定义了两个变量

private transient Object[] elementData;//数组

private int size;//长度