微信小程序开发收费,关键字优化策略,手机能建设网站吗,管城郑州网站建设Java的编程过程中经常会和Map打交道#xff0c;现在我们来一起了解一下Map的底层实现#xff0c;其中的思想结构对我们平时接口设计和编程也有一定借鉴作用。(以下接口分析都是以jdk1.8源码为参考依据) 1. Map An object that maps keys to values. A map cannot contain du…Java的编程过程中经常会和Map打交道现在我们来一起了解一下Map的底层实现其中的思想结构对我们平时接口设计和编程也有一定借鉴作用。(以下接口分析都是以jdk1.8源码为参考依据) 1. Map An object that maps keys to values. A map cannot contain duplicate keys;
each key can map to at most one value. Map提供三种访问数据的方式 键值集、数据集、数据-映射对应下表中的标记为黄色的三个接口。public interface MapK, V 方法名描述void clear()从此映射中移除所有映射关系可选操作。boolean containsKey(Object key)如果此映射包含指定键的映射关系则返回 true。boolean containsValue(Object value)如果此映射将一个或多个键映射到指定值则返回 true。SetMap.EntryK,V entrySet()返回此映射中包含的映射关系的 Set 视图。boolean equals(Object o)比较指定的对象与此映射是否相等。V get(Object key)返回指定键所映射的值如果此映射不包含该键的映射关系则返回 null。int hashCode()返回此映射的哈希码值。boolean isEmpty()如果此映射未包含键-值映射关系则返回 true。SetK keySet()返回此映射中包含的键的 Set 视图。V put(K key, V value)将指定的值与此映射中的指定键关联可选操作。void putAll(Map? extends K,? extends V m)从指定映射中将所有映射关系复制到此映射中可选操作。V remove(Object key)如果存在一个键的映射关系则将其从此映射中移除可选操作。int size()返回此映射中的键-值映射关系数。CollectionV values()返回此映射中包含的值的 Collection 视图。
在Java8中的Map有增添了一些新的接口不在上述表格之中这里不一一列举。
这里涉及到一个静态内部接口Map.EntryK,V 用于存储一个键值对该接口中设置set和get键值和value值的接口。 所以Map中存储数据都是以这种Entry为数据单元存储的。
2. AbatractMap
AbstractMap中增加了两个非常重要的成员变量
transient SetK keySet; transient CollectionV values;
通过这两个成员变量我们已经知道Map是如何存储数据的了键值存入keySet中value存入values中。由于Map需要保证键值的唯一性所以选择Set作为键值的存储结构而Value则对此没有任何要求所以选择Collection作为存储结构
AbstractMap实现了Map中的部分接口都是通过调用接口SetEntryK,V entrySet() 实现的而该接口的具体实现却留给了具体的子类。以下代码列出了equal()方法的具体实现 public boolean equals(Object o) {if (o this)return true;if (!(o instanceof Map))return false;Map?,? m (Map?,?) o;if (m.size() ! size())return false;try {IteratorEntryK,V i
entrySet().
iterator();while (i.hasNext()) {EntryK,V e i.next();K key e.getKey();V value e.getValue();if (value null) {if (!(m.get(key)null m.containsKey(key)))return false;} else {if (!value.equals(m.get(key)))return false;}}} catch (ClassCastException unused) {return false;} catch (NullPointerException unused) {return false;}return true;}3. HashMap
public class HashMapK,V extends AbstractMapK,V implements MapK,V, Cloneable, Serializable除了继承了AbstractMap中HashMap中的两个成员变量以外又增加了如下几个成员变量transient SetMap.EntryK,V entrySet;transient NodeK,V[] table;transient int size;transient int modCount;作为table存储的基本类型Node类的源码如下 View Code
Node是HashMap的一个内部类实现了Map.Entry接口本质是就是一个映射(键值对)。 建议看HashMap源码前了解一些散列表HashTable的基础知识http://www.cnblogs.com/NeilZhang/p/5651492.html 包括散列函数、碰撞处理、负载因子等。 3.1 hash值计算 static final int hash(Object key) { //jdk1.8 jdk1.7int h;// h key.hashCode() 为第一步 取hashCode值// h ^ (h 16) 为第二步 高位参与运算return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
} 首先获取key值的hash值每个类都有计算hash值的方法然后将该hash值的高16位异或低16位即得到散列值。
3.2 hash散列函数 通过hash函数可以得到key值对应的hash值那么如何通过该hash将key散列到hashtale中呢下面再介绍一个函数
对应的运算如下所示length为table的长度通常选择2^n
static int indexFor(int h, int length) { //jdk1.7的源码jdk1.8没有这个方法但是实现原理一样的return h (length-1); //第三步 取模运算
} 这里的取模运算等于 hash%length 然而运算比%运算的效率更高。
3.3 碰撞算法HashTable链表红黑树
当hash散列函数对不同的值散列到table的同一个位置该如何处理何时需要扩容table的大小分配一个更大容量的table
下面这张网络上流行的图基本解释了当发生碰撞时的处理办法 1、HashMap的主要存储为HashTable
2、当散列到的位置已经有元素存在时通过链表将当前元素链接到table中的元素后面
3、当链表长度太长默认超过8时链表就转换为红黑树利用红黑树快速增删改查的特点提高HashMap的性能。
红黑树的相关知识可以参考算法导论 第三部分——基本数据结构——红黑树
3.4 hashtable的扩容
这里先列出了HashMap源码中的几个常量 /*** 默认hashtable的长度 16*/static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16/*** hashtable的最大长度*/static final int MAXIMUM_CAPACITY 1 30;/*** hashtable的默认负载因子*/static final float DEFAULT_LOAD_FACTOR 0.75f;/*** 当Hashtable中链表长度大于该值时将链表转换成红黑树*/static final int TREEIFY_THRESHOLD 8; HashMap构造函数可以传入table的初始大小和负载因子的大小 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);this.loadFactor loadFactor;this.threshold
tableSizeFor(initialCapacity); } 这里有一个很巧妙牛逼的tableSizeFor算法返回一个大于等于且最接近 cap 的2的幂次方整数如给定9返回2的4次方16。它的具体实现全部通过位运算完成 /*** Returns a power of two size for the given target capacity.*/static final int tableSizeFor(int cap) {int n cap - 1;n | n 1;n | n 2;n | n 4;n | n 8;n | n 16;return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;}那么关键的问题什么时候会增大table的容量呢原来table中的Node如何重新散列到新的table中下面围绕这两个问题展开
HashMap中有个成员变量 threshhold当table中存放的node个数大于该值时就会调用resize()函数给table重新分配一个2倍的容量的数组具体可能涉及很多边界问题并且将原来table中的元素重新散列到扩容的新表中个人猜想这过程应该是非常耗时的所以为了避免HashTable不断扩容的操作使用者可以在构造函数的时候预先设置一个较大容量的table。
那么这个threshhold的值时如何计算的呢
1、构造函数的时候赋值 this.threshold tableSizeFor(initialCapacity);
2、resize()的时候 threshold也会随着table容量的翻倍而翻倍。
3、threshold 的初始值 DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
这里有个疑问 通过HashMap和HashMapintint两种构造函数得得到的threshold值计算方法不同前一种永远是table.length * 0.75 第二种是通过tableSizeFor(cap)计算所得为table.length 这时负载因子似乎失去了意义
HashTable重新散列
当重新分配了一个table时需要将原来table中的Node重新散列到新的table中。源码中针对hashtable、链表、红黑树中节点分别作了处理。
1. 如果是table中的值next为null直接映射到大的table中刚看的时候没理解为什么不需要判断如果新位置已经有元素怎么办
这里不需要考虑大的table中该节点已经有Node了比如和value | 1111 的元素只有一个table中不是链表那么 value | 11111 的元素也一定只有一个。1111为扩容前table长度减1,11111位扩容后table长度减1
在扩充HashMap的时候不需要像JDK1.7的实现那样
2、 如果是链表中的值则重新散列后他们可能有两种不同的值增加了一个异或位需要重新散列到两个位置。
java1.8 重新计算hash只需要看看原来的hash值新增的那个bit是1还是0就好了是0的话索引没变是1的话索引变成“原索引oldCap”HashMap的源码真的有太多精妙的地方了。
3、如果是红黑树中的节点重新散列后的值也可能出现两种需要对红黑数进行操作重新散列这一块没有具体看源码。
resize函数源码 View Code
3.5 put方法分析 介绍了上面的这么多下面分析put函数就不是那么难了 JDK1.8HashMap的put方法源码如下: 1 public V put(K key, V value) {2 // 对key的hashCode()做hash3 return putVal(hash(key), key, value, false, true);4 }56 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,7 boolean evict) {8 NodeK,V[] tab; NodeK,V p; int n, i;9 // 步骤①tab为空则创建
10 if ((tab table) null || (n tab.length) 0)
11 n (tab resize()).length;
12 // 步骤②计算index并对null做处理
13 if ((p tab[i (n - 1) hash]) null)
14 tab[i] newNode(hash, key, value, null);
15 else {
16 NodeK,V e; K k;
17 // 步骤③节点key存在直接覆盖value
18 if (p.hash hash
19 ((k p.key) key || (key ! null key.equals(k))))
20 e p;
21 // 步骤④判断该链为红黑树
22 else if (p instanceof TreeNode)
23 e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);
24 // 步骤⑤该链为链表
25 else {
26 for (int binCount 0; ; binCount) {
27 if ((e p.next) null) {
28 p.next newNode(hash, key,value,null);//链表长度大于8转换为红黑树进行处理
29 if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st
30 treeifyBin(tab, hash);
31 break;
32 }// key已经存在直接覆盖value
33 if (e.hash hash
34 ((k e.key) key || (key ! null key.equals(k)))) break;
36 p e;
37 }
38 }
39
40 if (e ! null) { // existing mapping for key
41 V oldValue e.value;
42 if (!onlyIfAbsent || oldValue null)
43 e.value value;
44 afterNodeAccess(e);
45 return oldValue;
46 }
47 }48 modCount;
49 // 步骤⑥超过最大容量 就扩容
50 if (size threshold)
51 resize();
52 afterNodeInsertion(evict);
53 return null;
54 } HashMap实际使用中注意点
当HashMap的key值为自定义类型时需要重写它的 equals() 和 hashCode() 两个函数才能得到期望的结果。如下例所示 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public class PhoneNumber { private int prefix; //区号 private int phoneNumber; //电话号 public PhoneNumber(int prefix, int phoneNumber) { this.prefix prefix; this.phoneNumber phoneNumber; } Override public boolean equals(Object o) { if(this o) { return true; } if(!(o instanceof PhoneNumber)) { return false; } PhoneNumber pn (PhoneNumber)o; return pn.prefix prefix pn.phoneNumber phoneNumber; } Override public int hashCode() { int result 17; result 31 * result prefix; result 31 * result phoneNumber; return result; } }
这里有个疑问 为什么在put() 一个元素时不直接调用equals() 判断集合中是否存在相同的元素而是先调用 hashCode() 看是否有相同hashCode() 元素再通过equal进行确认
答 这里是从效率的方面考虑的一个集合中往往有大量的元素如果一个个调用equals比较必然效率很低。如果两个元素相同他们的hashCode必然相等反之不成立先调用hashCode可以过滤大部分元素。 HashMap与ArrayMap的区别 由于HashMap在扩容时需要重建hash table 是一件比较耗时的操作为了优化性能Androd的系统中提供了ArrayMap当容量较小时ArrayMap的性能更优。 ArrayMap使用的是数组存放key值和value值扩容时只需要重建一个size*2的数组让后将之前的数据拷贝进去再新添新数据。但是ArrayMap也有缺点 它在每次put数据时如果这个key值map中不存在那么都可能会涉及到数组的拷贝操作。 HashMap每次put、delete操作不涉及扩容或者容量重新分配耗时较小但是扩容操作时较耗时。 ArrayMap每次put、delete操作耗时但是扩容操作不那么耗时。
参考
http://www.cnblogs.com/NeilZhang/p/5657265.html
http://www.importnew.com/20386.html
ArrayMap https://blog.csdn.net/hp910315/article/details/48634167
梦想不是浮躁,而是沉淀和积累
