文档章节

0005--jcf(jdk1.7)-HashMap源码

c
 cengy
发布于 2016/03/30 11:20
字数 2417
阅读 33
收藏 0

1.    HashMap的定义

HashMap实现了Map接口,允许Map的key为null和value为null。(除了不是同步的和允许null,其它是和Hashtable一样)。类定义如下:

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap继承了AbstractMap抽象类。这个抽象类提供了Map接口的大部分实现。可以通过继承这个类实现一个可以修改和不可修改的Map结构类。

HashMap内部是基于数组与链表结构。(链表解决碰撞问题,即哈希值冲突)。通过计算key值的散列码(hashCode)来计算元素的存储位置,如果计算出来的hashCode重了,即所谓hash冲突,那么HashMap通过链表来存放hash冲突的元素。

2.    HashMap的实现

HashMap的属性:

static final int DEFAULT_INITIAL_CAPACITY = 16;    // 默认初始容量
static final int MAXIMUM_CAPACITY = 1 << 30;    //最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;    //存储数据的数组
transient int size;         //key-value元素个数
int threshold;            //扩容判定threshold = capacity * load factor
final float loadFactor;    //加载因子
transient int modCount;

// 这两个属性是在抽象类AbstractMap中定义的
transient volatile Set<K>        keySet = null;
transient volatile Collection<V> values = null;

看一下存储数据的Entry类结构:

// 实现了Map.Entry接口
/**
 * Map.Entry接口:getKey(): K, getValue(): V, setValue(V): V
 *
 */
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;    // key
    V value;        // value
    Entry<K,V> next; // 当有hash冲突,存储的下一个元素
    final int hash; //hash值

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}
//所以从整个HashMap的声明可以看出它内部是通过数组+链表结构实现的

    HashMap的构造函数有4个:

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    // 注意这行,会一直计算capacity直到找到一个数=2的n次方,这个数最接近于initialCapacity。
    // 所以HashMap的大小初始大小可能不是initialCapacity。比如你传入initialCapcaity=7,那么这个HashMap的初始容量大小为8=2^3
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor); // 当超过这个threshold值(而不是超过capacity),HashMap将会扩容
    // 创建一个大小为capacity的Entry数组
    table = new Entry[capacity];
    init();// 所有的构造方法都会调用这个init()以及clone(),readObject()。在HashMap中是一个空方法
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}

// 构造一个含有指定key-value的HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAllForCreate(m);
}

private void putAllForCreate(Map<? extends K, ? extends V> m) {
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        putForCreate(e.getKey(), e.getValue());
}
// 这个方法用在构造方法中,它不会进行resize,以及进行conmodification检测等。它内部调用的是createEntry而不是addEntry方法。
private void putForCreate(K key, V value) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    int i = indexFor(hash, table.length);

    /**
     * Look for preexisting entry for key.  This will never happen for
     * clone or deserialize.  It will only happen for construction if the
     * input Map is a sorted map whose ordering is inconsistent w/ equals.
     */
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            e.value = value;
            return;
        }
    }

    createEntry(hash, key, value, i);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

3.    HashMap的重要方法

put(K, V): V
get(Object): V
remove(Object): V
  • put(K,  V) : 往Map中添加元素

// 内容有点像putForCreate(K,V),区别在上面已经提过
public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
        // HashMap不是将Entry对象中存储的对象的hashCode作为哈希值,而是将存储的key的hashCode进行计算得到哈希值。
    int hash = hash(key.hashCode());
    // 将hash值与数组长度做计算,找到存储的位置
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 如果找到了key,就替换掉存储的旧值,并返回旧值。
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    // 如果没有找到就在数组位置i处插入元素
    addEntry(hash, key, value, i);
    return null;
}

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
// 这个方法有点意思,或许我们实现的时候会直接与数组长度取余。
// 为什么需要这样计算在数组中的位置? 在HashMap的构造函数中,我们知道它的初始容量肯定是一个偶数,当length-1的时候,这个数的有效二进制位都是1。
// 这样只要保证了h的分散性就行。&用来取mod运算,效率比%高。
    return h & (length-1);
}
void addEntry(int hash, K key, V value, int bucketIndex) {

    Entry<K,V> e = table[bucketIndex];
    // 插入新元素。 注意: 这个元素是存放在Entry链表的第一个位置处的。它的next节点就是e。
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // 不会扩容了
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    // 如果发生扩容,需要重新计算在新数组中的位置
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}
// 具体实现将扩容前列表元素复制到新数组中,带Entry链的也依次复制到新Entry链
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}
  • get(Object): V

// 根据之前存储的方式计算hash,然后找到对应值,若没有找到返回null(注:如果value存放的是null,就不能判定是否找到没有)
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}
private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}
  • remove(Object): V

// 根据key删除元素,返回被删除的元素
public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            // 链表移动
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}

一些其它方法

clear()
containsKey(Object key) : boolean
containsValue(Object value): boolean
  • clear()

public void clear() {
    modCount++;
    Entry[] tab = table; 
    for (int i = 0; i < tab.length; i++)
        tab[i] = null;
    size = 0;
}
// 将map大小置为0,所有元素置空。
  • containsKey(Object): boolean

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}
  • containsValue(Object): boolean

public boolean containsValue(Object value) {
    if (value == null)
        return containsNullValue();

    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}

private boolean containsNullValue() {
    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (e.value == null)
                return true;
    return false;
}

对与是否包含某个value的时候,它会遍历整个数组以及对应的Entry链表,因此相对来说是比较费的

HashMap中关于key与value的操作

keySet(): Set<K>
values(): Collection<V>
entrySet(): Set<Map.Entry<K,V>>
  • keySet(): Set<K>

public Set<K> keySet() {
    Set<K> ks = keySet;
    return (ks != null ? ks : (keySet = new KeySet()));
}

// 这是一个私有内部类,继承了AbstractSet类(Set是不包含重复的元素)
private final class KeySet extends AbstractSet<K> {
    public Iterator<K> iterator() {
        return newKeyIterator();
    }
    public int size() {
        return size;
    }
    public boolean contains(Object o) {
        return containsKey(o);
    }
    public boolean remove(Object o) {
        return HashMap.this.removeEntryForKey(o) != null;
    }
    public void clear() {
        HashMap.this.clear();
    }
}

// KeySet中有个Iterator,它的实现类是KeyIterator。这个KeyIterator继承了HashIterator.HashIterator是HashMap的迭代类,它是一个抽象类,实现了Iterator接口,但没有实现next()方法。
// 可以说KeyIterator是HashItertor的一个子集,实现next()方法,返回下一个key值。
  • values(): Collection<V>

public Collection<V> values() {
    Collection<V> vs = values;
    return (vs != null ? vs : (values = new Values()));
}

private final class Values extends AbstractCollection<V> {
    public Iterator<V> iterator() {
        return newValueIterator();
    }
    public int size() {
        return size;
    }
    public boolean contains(Object o) {
        return containsValue(o);
    }
    public void clear() {
        HashMap.this.clear();
    }
}
// Values也是一个私有内部类,继承了AbstractCollection类。
// Values类中的迭代器同KeyIterator一样继承自HashIerator,实现next()方法,返回下一个value值。
  • entrySet() : Set<Map.Entry<K,V>>

public Set<Map.Entry<K,V>> entrySet() {
    return entrySet0();
}

private Set<Map.Entry<K,V>> entrySet0() {
    Set<Map.Entry<K,V>> es = entrySet;
    return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<K,V> e = (Map.Entry<K,V>) o;
        Entry<K,V> candidate = getEntry(e.getKey());
        return candidate != null && candidate.equals(e);
    }
    public boolean remove(Object o) {
        return removeMapping(o) != null;
    }
    public int size() {
        return size;
    }
    public void clear() {
        HashMap.this.clear();
    }
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
    public Map.Entry<K,V> next() {
        return nextEntry();
    }
}
// Map.Entry是一个接口。提供了返回key与value的方法。
// nextEntry是HashIterator中的一个方法,返回下一个Entry。返回的Entry是Map.Entry的一个实现类。见开始部分Entry

5    关于HashMap的一些常见问题

    1)HashMap的实现原理(参见put方法的实现,get方法的实现)

    2)如果我们要插入元素的key的hashCode值相等会覆盖吗? 不会,会是一个Entry链存储(见put方法的实现)

    3)如果key的hasCode相同,怎么获取值对象?根据key的hashCode计算出在table中的位置,然后取值对象(比较key是否相等)。内部存储的是Entry,包含了key与value(见get方法的实现)

【参考】

*    http://www.importnew.com/7099.html





© 著作权归作者所有

c
粉丝 1
博文 22
码字总数 16864
作品 0
成都
私信 提问
JDK1.8 不一样的HashMap

前言 HashMap想必大家都很熟悉,JDK1.8 的 HashMap 随便一搜都是一大片一大片的,那为什么还要写呢,我会把它精简一下,一方面有利于自己的学习,另一方面希望让大家更好理解核心内容。本篇主...

小坏怎么被用了
2018/01/05
0
0
jdk1.7hashMap源码分析

1.8的源码分析在这里:jdk1.8hashMap源码分析 jdk1.7的map接口结构: jdk1.8的map接口结构: hashMap继承关系: hashTable继承结构: concurrentHashMap继承关系: 哈哈,我比较懒,不想画图...

小小明童鞋
2018/10/19
78
0
Java 8系列之重新认识HashMap

转自:美团点评技术团队--Java 8系列之重新认识HashMap 摘要 HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashM...

放了一周的酸梅汤
2017/11/05
0
0
Java面试必问之---HashMap

   本文有些长,贴的源码较多,请各位看官自备花生瓜子啤酒饮料矿泉水小板凳,且听我慢慢道来。    Java面试都会问集合,集合必问HashMap,CurrentHashMap,后面的套路就肯定会问多线程...

Marksmanbat
2018/08/17
0
0
JDK7 和 JDK8 HashMap效率分析

JDK源码深揪,JDK1.7版本 和 JDK1.8版本比较。 以前写过JDK1.8 HashMap源码解析,这次就看看以前JDK1.7 HashMap的实现 以及 JDK7和JDK8的HashMap效率方面的比较,JDK8 HashMap效率真的比JDK...

荧光牧人
2018/01/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部