甘肃龙网

  1. 首页 > 生活 > >

源码解析 HashMap底层实现和原理( 二 )

生活百科数组


里面实现一个静态内部类Entry，其重要的属性有 hash，key，value，next 。
里面用到链式数据结构的一个概念 。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry 。打个比方，第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A 。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起 。所以疑问不用担心 。也就是说数组中存储的是最后插入的元素 。到这里为止，的大致实现，我们应该已经清楚了 。
public V put(K key, V value) {if (key == null)return putForNullKey(value); //null总是放在数组的第一个链表中int hash = hash(key.hashCode());int i = indexFor(hash, table.length);//遍历链表for (Entry e = table[i]; e != null; e = e.next) {Object k;//如果key在链表中已存在，则替换为新valueif (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = http://www.kingceram.com/post/e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, key, value, i);return null;}void addEntry(int hash, K key, V value, int bucketIndex) {Entry e = table[bucketIndex];table[bucketIndex] = new Entry(hash, key, value, e); //参数e, 是Entry.next//如果size超过threshold，则扩充table大小 。再散列if (size++ >= threshold)resize(2 * table.length);}
四、重要方法深度解析 1、构造方法
HashMap()//无参构造方法HashMap(int initialCapacity)//指定初始容量的构造方法 HashMap(int initialCapacity, float loadFactor) //指定初始容量和负载因子HashMap(Map m)//指定集合，转化为HashMap
提供了四个构造方法，构造方法中 ，依靠第三个方法来执行的，但是前三个方法都没有进行数组的初始化操作，即使调用了构造方法此时存放中数组元素的table表长度依旧为0。在第四个构造方法中调用了()方法完成了table的初始化操作，并将m中的元素添加到中 。
2、添加方法
public V put(K key, V value) {if (table == EMPTY_TABLE) { //是否初始化inflateTable(threshold);}if (key == null) //放置在0号位置return putForNullKey(value);int hash = hash(key); //计算hash值int i = indexFor(hash, table.length);//计算在Entry[]中的存储位置for (Entry e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = http://www.kingceram.com/post/e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, key, value, i); //添加到Map中return null;}

源码解析 HashMap底层实现和原理

文章插图
在该方法中，添加键值对时，首先进行table是否初始化的判断，如果没有进行初始化（分配空间，Entry[]数组的长度） 。然后进行key是否为null的判断，如果key==null ,放置在Entry[]的0号位置 。计算在Entry[]数组的存储位置，判断该位置上是否已有元素，如果已经有元素存在，则遍历该Entry[]数组位置上的单链表 。判断key是否存在，如果key已经存在，则用新的value值，替换点旧的value值，并将旧的value值返回 。如果key不存在于中，程序继续向下执行 。将key-vlaue, 生成Entry实体，添加到中的Entry[]数组中 。
3、()
/** hash hash值* key 键值* value value值* bucketIndex Entry[]数组中的存储索引* / void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length); //扩容操作，将数据元素重新计算位置后放入newTable中，链表的顺序与之前的顺序相反hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}void createEntry(int hash, K key, V value, int bucketIndex) {Entry


上一篇：mysql字符串排序规则_MySQL字符集和排序规则

下一篇：Unsatisfied dependency expressed through