频道栏目
首页 > 程序开发 > 移动开发 > 其他 > 正文
1.7 HashMap源码分析
2017-07-28 13:55:41         来源:weixin_36234344的博客  
收藏   我要投稿

1.7  HashMap源码分析,最近准备面试,整理一下知识点,虽然hashmap的源码在网上都已经快翻烂了,但是自己再写一遍也会加深一下记忆,再走一遍源码,就感觉hashmap是自己写的对不对!

之后我也会分析一下1.8的hashmap的源码!好了 屁话不多说,开始我们源码分析!

1.基本属性

    static final int DEFAULT_INITIAL_CAPACITY = 16;//默认容量
    static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量2的30次幂,超过这个容量用之替换
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子0.75
    transient Entry[] table;//Entry数组保存键值对
    transient int size;      //键值对的数量
    int threshold;      //扩容的阈值 等于负载因子乘以容量
    final float loadFactor;   //负载因子实际大小
    transient int modCount;    //HashMap被改变的次数

2.构造函数

  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;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
 
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    public HashMap(Map m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }
4个构造函数最终都会重载第一个构造函数

3.求hash值

  final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;//随机hash值
        }

        h ^= k.hashCode();h与对象k的hashcode异或

        //这段代码叫扰动函数,做了4次移位操作以及4次异或操作
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
代码中的扰动函数起到了混合hash值中的高位代码与低位代码作用,增大了hash值低位的随机性,,防止hash值低位出现规律性,减少了冲突。

4.求hash值对应数组坐标

  static int indexFor(int h, int length) {
        return h & (length-1);
    }
使用&代替取模,提高效率,也因为这个原因,使得hashmap以二倍扩容,因为数组长度如果为奇数,length-1就为偶数,末尾就为0,则对应下标取值全部会投影到偶数下标,增大冲突发生的可能,因此 以2的倍数扩容,使得length为偶数,减少冲突发生的次数。

5.get方法

  public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
如果key为空,则查找key==null的value ,这也说明了hashmap的key支持为空
  private V getForNullKey() {
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }
如果key不为空,先找到entry节点
  final Entry getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        for (Entry 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;
    }
求key的hash值然后根据hash值找到再table中的下表,返回table节点数组中的头节点。

6. put方法

如果key不为空,先定位table数组下标,如果hash值与table数组中的某个节点相等,且key也相等,更改value值并返回,如果没有相等的则插入节点,头插

 public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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 = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

如果 key为空 ,将键值对插入table[0]下标处,头插
 private V putForNullKey(V value) {
        for (Entry 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;
    }

插入节点时如果大小大于阈值时2倍扩容,

  void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }


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

7.扩容方式
  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];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
创建2倍容量的新数组,将旧数组中的数据重新计算数组索引加入到新数组中
点击复制链接 与好友分享!回本站首页
上一篇:IAR中map文件全解析
下一篇:解析HttpUtil--post方法
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站