`
iluoxuan
  • 浏览: 579946 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

HashMap源码

 
阅读更多

1:参考

http://www.ibm.com/developerworks/cn/java/j-lo-hash/

 

3:java map对比性能

http://blog.hongtium.com/java-map-skiplist/

 

 测试例子:

 

public class MapTest {

    @Test
    public void hashMapTest() {
        Map<String, Object> map=new HashMap<String, Object>();
        map.put(null, null);
        map.put("a", null);
        map.put(null, "a");
        map.put("b", "b");
        map.put("b", "abccccccccccc");
        System.out.println(map.get(null));
        System.out.println(map.get("a"));
        System.out.println(map.get("b"));
    }
}
 

 

2: HashMap的结构关系:

 

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

 

  3:Map<K,V> 接口定义了一些map的方法

 

public interface Map<K,V> {
    boolean isEmpty();
    boolean containsKey(Object key);
    V put(K key, V value);
    V remove(Object key);
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();

   //保存map数据类型的接口 
    interface Entry<K,V> {
    	
	K getKey();	
	V getValue();
	V setValue(V value);
	boolean equals(Object o);
	int hashCode();
    }

    boolean equals(Object o);
    int hashCode();
}
 

 4:AbstractMap<K,V>是TreeMap和hashMap等具体实现的父类 抽象, 具体的put 和get操作子类具体实现

 

5:map.put(null, null)或者map.put(null, "aaa") 对null key的处理

源码:

    

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value); // 处理key值为null的情况
        int hash = hash(key.hashCode()); // 根据类型的hashcode值算hash,使得h
       //使得hash的发布更加均匀 减少重复
        int i = indexFor(hash, table.length); //获取对象的保存位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) { //已经有key了
            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;
    }

  HashMap可以处理key为null的情况,在putForNullKey(value)中

  

 private V putForNullKey(V value) { 
        for (Entry<K,V> e = table[0]; e != null; e = e.next) { 
// 在下表0处理保存null的值,如果e不为空,处理冲突
            if (e.key == null) { // 是否已经存在 替换新的value
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0); // 在下表0处添加key为null的value
        return null;
    }

  HashMap的key为null,的put过程就到此结束.

   

   下面看下key不为null的情况,更具key.hashCode的方法使用hash()函数计算,hash值,看下hash()

   

    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);
    }

   这个hash()的目的,是因为key.hashCode()的计算出来的重复可能性比较高,所以hash一次减少重复,具体为什么要这样写,也不太明白?据说是《计算机程序设计艺术》里有这个解释,增加了hash的随机分布性。

   int i = indexFor(hash, table.length); //获取对象的在数组中保存位置

 hash()后的值,可能比table.length大很多; 怎么保证hash()后的在数组的范围之内;hash() % table.length 也是可以,但是 效率肯定是没有& 位移的操作快,

 

  /**
     * 返回对象的保存位置
     * lengt为2的倍数
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 所有在动态扩展数组大小的时候都是2的倍速

如果是key是的value是空 就会走

 addEntry(hash, key, value, i);

 

 void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length); //重新申请空间
    }

 

Entry<K, V>结构:

 

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;  // 链表的形式HASH处理冲突
        final int hash;

        /**
         * Creates new entry.
         * 创建一个--
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
	    V oldValue = value;
            value = newValue;
            return oldValue;
        }
        
    }

 

数组空间满了, 必须要重新分配空间: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); // 容量大小
    }

 

上面没有说到的是 new HashMap()

 

 

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

static final float DEFAULT_LOAD_FACTOR = 0.75f; //hash的装载因子

 

复制老数据到新的

    /**
     * Transfers all entries from current table to newTable.
     */
    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);
            }
        }
    }

 

HashMap取数据,可以自己看下;如果hashCode很不好,会导致hashmap在列表中取数据让其退化成链表,则是O(N).即便是O(1),也要注意,实际上计算hash用了好几步,绝对比直接从数组中获取某个元素的O(1)时间要长的多。

 

hashmap的优化:

1: 由于hashmap的容量,受限于loadfactor*capacity=thredload,然后进行扩容,重新hash

所以对可以预知的容量,最好new HashMap(18), 避免扩容操作

2: 当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。

掌握了上面知识之后,我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子。通常情况下,程序员无需改变负载因子的值。

如果开始就知道 HashMap 会保存多个 key-value 对,可以在创建时就使用较大的初始化容量,如果 HashMap 中 Entry 的数量一直不会超过极限容量(capacity * load factor),HashMap 就无需调用 resize() 方法重新分配 table 数组,从而保证较好的性能。当然,开始就将初始容量设置太高可能会浪费空间(系统需要创建一个长度为 capacity 的 Entry 数组),因此创建 HashMap 时初始化容量设置也需要小心对待。

上面说法是相对的,负载因子大,hash冲突可能会增加,查询效率可能下降; 小的 扩容比较频繁

怎么很好的讲解原理:

面试的时候:

1:

 

 

 

 

 

 

分享到:
评论

相关推荐

    HashMap源码深度剖析.md

    HashMap源码深度剖析,面试必备

    HashMap源码(JDK1.7,含注释)

    HashMap源码(JDK1.7,含注释)

    1.6 hashmap源码

    hashmap源码,可以看看http://blog.csdn.net/wabiaozia/article/details/50684556

    HashMap源码(上)

    HashMap的部分源码解析

    HashMap源码流程图

    HashMap源码流程图 一图解析HashMap源码流程 // 默认的HashMap中数组的长度 16 static final int DEFAULT_INITIAL_CAPACITY = 1 ; // aka 16 // HashMap中的数组的最大容量 static final int MAXIMUM_CAPACITY = 1 ...

    JDK7HashMap源码

    精确的版本号是jdk-7u80。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。

    HashMap源码剖析共10页.pdf.zip

    《HashMap源码剖析》 HashMap是Java编程语言中一个非常重要的数据结构,它属于集合框架的一部分,提供了键值对(Key-Value)的存储方式。HashMap在内部使用了一个数组和链表来实现,实现了快速的查找、插入和删除...

    JDK8HashMap源码

    精确的版本号是jdk-8u181。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。

    手写HashMap源码.rar

    《手写HashMap源码解析——深入理解数据结构与算法》 HashMap是Java编程语言中一个常用的集合类,它提供了一种高效、灵活的键值对存储方式。在面试过程中,尤其是2020年及以后的技术面试中,深入理解HashMap的实现...

    面试必考之HashMap源码分析与实现

    在Java编程语言中,HashMap是集合框架中一个重要的类,用于存储键值对的数据结构。面试中,HashMap的源码分析与实现是一个常见的考察点,...深入学习和实践HashMap源码,能够帮助我们更好地理解和优化Java应用程序。

    HashMap源码实现红黑树添加元素和删除元素

    HashMap 源码实现红黑树添加元素和删除元素 HashMap 中使用红黑树来存储元素,是为了提高查找、插入和删除操作的性能。红黑树是一种自平衡二叉树,可以保持二叉树的平衡,从而获得较高的查找性能。 红黑树的创建...

    HashMap源码分析

    HashMap 是 Java 中最常用的集合类之一,它是基于哈希表实现的,提供了高效的数据存取功能。HashMap 的核心原理是将键(key)通过哈希函数转化为数组索引,然后将键值对(key-value pair)存储在数组的对应位置。...

    java7hashmap源码-java:Java

    hashmap源码 Table Of Contents day01_JAVA语言概述与基本语法:标识符、变量也变量分类、源码_反码_补码、进制转换、编码与字符集 day02_基本语法.运算符:算术运算符、赋值运算符、比较运算符、逻辑运算符、位...

    1.面试必考之HashMap源码分析与实现 伸缩性角度看HashMap的不足

    1.面试必考之HashMap源码分析与实现 伸缩性角度看HashMap的不足

    HashMap源码,,,,,,写个笔记方便后续学习

    HashMap源码,,,,,,写个笔记方便后续学习

    HashMap 源码分析

    《HashMap 源码解析——JDK11版本》 HashMap是Java中广泛使用的非同步散列表,其设计和实现是高效且灵活的。在JDK1.8之前,HashMap的底层数据结构采用的是数组+链表的方式,这种方式称为“拉链法”来解决哈希冲突。...

Global site tag (gtag.js) - Google Analytics