【Java基础】Hashmap

简介: 【Java基础】Hashmap

  hashMap实现Map接口,基于hashing原理,以键值对形式存储,允许null键/值,非同步的集合类型;

    hashmap的底层存储结构是基于数组和链表的


2018093020234487.png


一、put方法



public Object put(Object key,Object value);


1、因为hashmap存储的底层结构是数组和链表,所以,当我们put时,需要计算出数组的下标:


1)执行key.hashCode()方法,得到哈希码:hashCode=key.hashCode();


2)用哈希码做hash运算,得到一个散列值:int hash = hash(hashCode);


3)散列值与数组的长度做indexFor运算,得到数组下标。


2、了解了这个过程,我们很容易能发现,即使key不同,经过前两步运算,也可能得到相同散列值。所以我们put时,新的entry和旧的entry可能发生冲突,解决hash冲突的方法有很多,在hashmap中采用的是链地址法。即:


对新entry和旧entry进行判断:


1)散列值相同,key相同;


此时说明是相同的entry,用新的entry覆盖旧的entry。


2)散列值相同,key不同;


执行key.equals()方法;


如果这两个对象通过hashmap重写的equals()方法判断是一样的,说明是同一个entry对象,用新的entry覆盖旧的entry;


如果不同,就把新加入的entry对象放在对应数组下标位置的表头,早进来的entry向后移动一个位置,形成链表;


特别注意:我们存放在数组中的并不只有value,是一个entry(hash,key,value,bucketIndex)对象。


3、链表长度太长,影响查询效率怎么办?


JDK1.8多了一个新特性,当链表的长度>=8时,链表转换为红黑树,提高查询效率:


 1.8 链表转红黑树的源码
static final int TREEIFY_THRESHOLD = 8;
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
          treeifyBin(tab, hash);
             break;



4、不断增加对象,是否需要扩容resize?


了解一下API里hashmap的构造方法,里面有initialCapacity和loadFactor两个名词;


initialCapacity是哈希表的数组的初识大小,始终保持 2^n,可以扩容,扩容后数组大小为当前的 2 倍;loadFactor是加载因子;HashMap的默认大小是16,那么他的数组长度是0-15;默认加载因子是0.75;threshold:扩容的阈值,等于 capacity * loadFactor


所以,当容量达到threshold时,数组会自动扩容到原来大小的两倍;比如,当前我们的数组的大小是16,当存储到12个元素时,数组会自动扩容到32.

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


 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)(newCapacity * loadFactor);
     }


5、key为null时

 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<K,V> 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;
   }
 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;  
 }  



当key为null时,如果数组中有key为null的,遍历table[0]链表(key为null的元素放在了数组的第0位),如果找到,将传入的value重新赋值给这个元素的value,并返回原来的value。如果没有找到,就将元素添加到table[0]链表的表头。所以,key为null时,在hashmap的链表中只有一个值。



二、get

1、与put相同,先根据key,算出hash,算出数组下标,定位到数组元素。


2、遍历该元素处的链表

取出传进来的key与链表中entry对象的key值相等的value或传进来的key和entry对象的key连重写后的equals后都一样的value;

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

3、当key为null时?

由put的过程可知,hashmap将key为null的元素放到了数组第0个元素的链表中。根据getForNullKey()的实现代码可知。

 


相关文章
|
16天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
28 1
|
18天前
|
存储 安全 Java
Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
【10月更文挑战第17天】Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
45 2
|
18天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
49 2
|
18天前
|
存储 缓存 安全
HashMap VS TreeMap:谁才是Java Map界的王者?
HashMap VS TreeMap:谁才是Java Map界的王者?
56 2
|
1天前
|
Java
Java之HashMap详解
本文介绍了Java中HashMap的源码实现(基于JDK 1.8)。HashMap是基于哈希表的Map接口实现,允许空值和空键,不同步且线程不安全。文章详细解析了HashMap的数据结构、主要方法(如初始化、put、get、resize等)的实现,以及树化和反树化的机制。此外,还对比了JDK 7和JDK 8中HashMap的主要差异,并提供了使用HashMap时的一些注意事项。
Java之HashMap详解
|
15天前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
38 5
|
1月前
|
Java
用java搞定时任务,将hashmap里面的值存到文件里面去
本文介绍了如何使用Java的`Timer`和`TimerTask`类创建一个定时任务,将HashMap中的键值对写入到文本文件中,并提供了完整的示例代码。
34 1
用java搞定时任务,将hashmap里面的值存到文件里面去
|
16天前
|
存储 Java API
详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
【10月更文挑战第19天】深入剖析Java Map:不仅是高效存储键值对的数据结构,更是展现设计艺术的典范。本文从基本概念、设计艺术和使用技巧三个方面,详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
35 3
|
16天前
|
存储 缓存 安全
在Java的Map家族中,HashMap和TreeMap各具特色
【10月更文挑战第19天】在Java的Map家族中,HashMap和TreeMap各具特色。HashMap基于哈希表实现,提供O(1)时间复杂度的高效操作,适合性能要求高的场景;TreeMap基于红黑树,提供O(log n)时间复杂度的有序操作,适合需要排序和范围查询的场景。两者在不同需求下各有优势,选择时需根据具体应用场景权衡。
22 2
|
16天前
|
存储 安全 Java
Java Map新玩法:深入探讨HashMap和TreeMap的高级特性
【10月更文挑战第19天】Java Map新玩法:深入探讨HashMap和TreeMap的高级特性,包括初始容量与加载因子的优化、高效的遍历方法、线程安全性处理以及TreeMap的自然排序、自定义排序、范围查询等功能,助你提升代码性能与灵活性。
23 2