Map原理及使用

Hashmap

原理

hashmap的底层数据结构散列表，即：数组+链表，创建的时候初始化一个数组，每个节点可以为一个链表

 当一键值对发生put操作时，

首先根据key的hash值得到这个元素在数组中的位置（即下标），如果这个位置上已经存在其他元素，将进行下一步操作。

 

1. 由于同一点是链表方式存储，会将原来的元素向后推
2. 然后新的元素放在这个位置上

put操作可能会出现冲突，冲突分两种：

 

1. 不同的key值，通过hash函数得出相同的index，这种冲突通过上面所说的链表方式存储。
2. 相同的key值，直接覆盖。

所以为了减少冲突，尽量将hashmap 的长度设置为2的次方，因为如果不是2的次方，经过hash & 操作，最后一位总是0如下图，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，而且这样可以使用的位置比数组长度小了很多，增加了冲突的几率，故减慢的查询的效率（如果每一个节点都不存在链表，则不需要循环，查询效率会高，所以尽量均匀分布）。

 

同理，当一键值对发生get操作时，会经过hash函数计算得到index，如果节点为链表有多个元素，则迭代用key.equals()比较获取。

 

容量

源码多了恶心，少量如下：

 

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

 三个常量中可以看出，默认的容器大小是16，最大长度是2的30次方，load factor默认是0.75，扩充的临界值是16*0.75=12，

 

如果put操作检测出hashmap的容量不足，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元个数能够有效的提高hashmap的性能。

实战总结

所以如果我们想初始化一个容量大小为13的容量，合理的方式是什么呢？

1.Map<String, String> map1 = new HashMap<>(13);
2.Map<String, String> map2 = new HashMap<>(13, 1);
3.Map<String, String> map3 = Maps.newHashMapWithExpectedSize(13);

以上是三种初始化方式

第一种

直接根据构造方法初始化，那么map会初始化一个容量大小为16的map，在超过16*0.75即12的时候发生扩容，这显然不是我们想看到的。

第二种

在构造容量为13的基础上，将负载因子的值设为1，那么map将会在超过16个元素后开发扩容，可以满足我们的预期效果，但这种情况一旦发生扩容，随着元素的增多，碰撞的几率就会升高，链表就会很长，这样就大大的降低了性能。

第三种

使用guava的方式初始化一个map，根据源码发现guava已经帮我算好了，真正需要扩容的临界点，

可以满足我们的期望，同时也不需要修改负载因子的值，所以无特殊情况下，建议使用此方式。

LinkedHashMap

其底层实现基本与hashmap一致，但是linkedHashMap多维护了一张双向的链表

 LinkedHashMap成员变量

增加accessOrder属性，默认为false，当为false时，按插入顺序排序，当为true时，

按LRU+插入顺序排序

LRU：最近最少使用算法

Entry

 

其保存的Entry对象增加了两个属性，before和after

 存数据

 

LinkedHashMap没有重写put方法，而是重写了addEntry()方法，把新的Entry也加到header

 

链表结构里面去

 

 

取数据

 

1、先调用hashmap的getEntry()方法获取Entry

 当accessOrder为true时，把最近使用的当前Entry移到header的before位置，而LinkedHashIterator遍历的方式是从header.after开始遍历，先得到最近使用的Entry

 

最近使用：accessOrder为true时，get(Object key)方法会导致Entry最近使用put(K key, V value)/putForNullKey(value)只有是覆盖操作时会导致Entry最近使用。它们都会触发recordAccess方法从而导致Entry最近使用

 

 删除

 

LinkedHashMap没有重写remove(Object key)方法，重写了被remove调用的recordRemoval方法，删除了双向链表中的before和after。

HahsMap remove(Object key)把数据从横向数组 * 竖向next链表里面移除之后（就已经完成工作了，所以HashMap里面recordRemoval是空的实现调用了此方法

 LinkedHashMap的遍历

 总结

 

1、什么是LRU+插入顺序？

put(K key, V value)/putForNullKey(value)只有是覆盖操作时会导致Entry最近使用，即为插入顺序；accessOrder为true时，get(Object key)方法会导致Entry最近使用，即为LRU

2、LinkedHashMap和HashMap的区别

• LinkedHashMap继承HashMap，结构2里数据结构的变化交给HashMap就行了。
• 结构1里数据结构的变化就由LinkedHashMap里重写的方法去实现。
• 简言之：LinkedHashMap比HashMap多维护了一个链表。