jdk7 中HashMap的知识点总结

HashMap中的几个重要变量

默认初始容量,必须是2的n次方

static final int DEFAULT_INITIAL_CAPACITY = 16;

最大容量,当通过构造方法传入的容量比它还大时,就用这个最大容量,必须是2的n次方

static final int MAXIMUM_CAPACITY = 1 << 30;

默认负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

用来存储键值对,可以看到键值对都是存储在Entry中的

transient Entry<K,V>[] table;

//capacity * load factor,超过这个数就会进行再哈希
int threshold;

HashMap中的元素是用名为table的Entry数组来保存的,默认大小是16

  • capacity:数组的容量
  • load_factor:负载因子
  • threshold:实际能承载的容量,等于上面两个相乘,当size大于threshold时,就会进行rehash

jdk7中在面对key为String的时候采用了区别对待,会有alternative hashing,但是这个在jdk8中已经被删除了

存储结构

Entry是一个链表结构,不仅包含key和value,还有可以指向下一个的next

static class Entry<K,V> implements Map.Entry<K,V> {
 final K key;
 V value;
 Entry<K,V> next;
 int hash;

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

put方法

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

首先通过hash方法对hashcode进行处理:

final int hash(Object k) {
 int h = 0;
 h ^= k.hashCode();

 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
 }

可以看到只是在key的hashcode值上做了一些处理,通过hash计算出来的值将会使用indexFor方法找到它应该所在的table下标:

static int indexFor(int h, int length) {
 return h & (length-1);
 }

这个方法其实相当于对table.length取模。

当需要插入的key为null时,调用putForNullKey方法处理:

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

putForNullKey方法只从table[0]这个位置开始遍历,因为key为null只放在table中的第一个位置,下标为0,在遍历中如果发现已经有key为null了,则替换新value,返回旧value,结束;如果还没有key为null,调用addEntry方法增加一个Entry:

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

可以看到jdk7中resize的条件已经发生改变了,只有当 size>=threshold并且 table中的那个槽中已经有Entry时,才会发生resize。即有可能虽然size>=threshold,但是必须等到每个槽都至少有一个Entry时,才会扩容。还有注意每次resize都会扩大一倍容量

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

最后看createEntry,它先保存这个桶中的第一个Entry,创建新的Entry放入第一个位置,将原来的Entry接在后面。这里采用的是头插法插入元素。

get方法

其实get方法和put方法如出一辙,怎么放的怎么拿

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

 return null == entry ? null : entry.getValue();
 }

key为null时,还是去table[0]去取:

private V getForNullKey() {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  if (e.key == null)
  return e.value;
 }
 return null;
 }

否则调用getEntry方法:

final Entry<K,V> getEntry(Object key) {
 int hash = (key == null) ? 0 : hash(key);
 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;
 }

这个方法也是通过key的hashcode计算出它应该所在的下标,再遍历这个下标的Entry链,如果key的内存地址相等(即同一个引用)或者equals相等,则说明找到了

hash的原则

A、等幂性。不管执行多少次获取Hash值的操作,只要对象不变,那么Hash值是固定的。如果第一次取跟第N次取不一样,那就用起来很麻烦.

B、对等性。若两个对象equal方法返回为true,则其hash值也应该是一样的。举例说明:若你将objA作为key存入HashMap中,然后new了一个objB。在你看来objB和objA是一个东西(因为他们equal),但是使用objB到hashMap中却取不出来东西。

C、互异性。若两个对象equal方法返回为false,hash值有可能相同,但最好是不同的,这个不是必须的,只是这样做会提高hash类操作的性能(碰撞几率低)。

解决hash碰撞的方法:

  • 开放地址法
  • 链地址法

hashmap采用的就是链地址法,这种方法好处是无堆积现象,但是next指针会占用额外空间

和jdk8中的HashMap区别

在jdk8中,仍然会根据key.hashCode()计算出hash值,再通过这个hash值去定位这个key,但是不同的是,当发生冲突时,会采用链表和红黑树两种方法去处理,当结点个数较少时用链表(用Node存储),个数较多时用红黑树(用TreeNode存储),同时结点也不叫Entry了,而是分成了Node和TreeNode。再最坏的情况下,链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。jdk8中的HashMap中定义了一个变量TREEIFY_THRESHOLD,当节点个数>= TREEIFY_THRESHOLD - 1时,HashMap将采用红黑树存储

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。

(0)

相关推荐

  • javascript实现的HashMap类代码

    复制代码 代码如下: <script language = "javascript" > function HashMap() {     /**Map大小**/     var size = 0;     /**对象**/     var entry = new Object();     /**Map的存put方法**/     this.put = function(key, value) {         if (!this.containsKey(key)) {

  • Android中实现HashMap排序的方法

    HashMap排序是数据结构与算法中常见的一种排序算法.本文即以Android平台为例来实现该算法. 具体代码如下: public static void main(String[] args) { Map<String, Integer> map = new HashMap<String, Integer>(); map.put("lisi", 5); map.put("lisi1", 1); map.put("lisi2&quo

  • java遍历HashMap简单的方法

    本文实例讲述了java遍历HashMap简单的方法.分享给大家供大家参考.具体实现方法如下: import java.util.HashMap; import java.util.Iterator; import java.util.Set; public class HashSetTest { public static void main(String[] args) { HashMap map = new HashMap(); map.put("a", "aa"

  • java中Hashtable和HashMap的区别分析

    1.Hashtable是Dictionary的子类, 复制代码 代码如下: public class Hashtable<K,V>     extends Dictionary<K,V>     implements Map<K,V>, Cloneable, java.io.Serializable HashMap: 复制代码 代码如下: public class HashMap<K,V>    extends AbstractMap<K,V> 

  • Java中HashMap和Hashtable及HashSet的区别

    Hashtable类   Hashtable继承Map接口,实现一个key-value映射的哈希表.任何非空(non-null)的对象都可作为key或者value. 添加数据使用put(key,value),取出数据使用get(key),这两个基本操作的时间开销为常数. Hashtable通过initial   capacity和load   factor两个参数调整性能.通常缺省的load   factor   0.75较好地实现了时间和空间的均衡.增大load   factor可以节省空间但

  • 浅析Java中Map与HashMap,Hashtable,HashSet的区别

    HashTable和HashMap区别 第一,继承的父类不同.Hashtable继承自Dictionary类,而HashMap继承自AbstractMap类.但二者都实现了Map接口. 复制代码 代码如下: public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, Serializable public class HashMap<K,V>extends

  • 解析WeakHashMap与HashMap的区别详解

    WeakHashMap,此种Map的特点是,当除了自身有对key的引用外,此key没有其他引用那么此map会自动丢弃此值,见实例:此例子中声明了两个Map对象,一个是HashMap,一个是WeakHashMap,同时向两个map中放入a.b两个对象,当HashMap  remove掉a 并且将a.b都指向null时,WeakHashMap中的a将自动被回收掉.出现这个状况的原因是,对于a对象而言,当HashMap  remove掉并且将a指向null后,除了WeakHashMap中还保存a外已经

  • JAVA HashMap详细介绍和示例

    第1部分 HashMap介绍HashMap简介HashMap 是一个散列表,它存储的内容是键值对(key-value)映射.HashMap 继承于AbstractMap,实现了Map.Cloneable.java.io.Serializable接口.HashMap 的实现不是同步的,这意味着它不是线程安全的.它的key.value都可以为null.此外,HashMap中的映射不是有序的.HashMap 的实例有两个参数影响其性能:"初始容量" 和 "加载因子".容量

  • Java中HashMap和TreeMap的区别深入理解

    首先介绍一下什么是Map.在数组中我们是通过数组下标来对其内容索引的,而在Map中我们通过对象来对对象进行索引,用来索引的对象叫做key,其对应的对象叫做value.这就是我们平时说的键值对. HashMap通过hashcode对其内容进行快速查找,而 TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的). HashMap 非线程安全 TreeMap 非线程安全 线程安全 在Java里,线程安全一般体

  • java HashMap通过value反查key的代码示例

    复制代码 代码如下: import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.Set;public class MapValueGetKey {  public static void main(String[] args) {    Map map = new HashMap<>();    map.put(1,&qu

随机推荐