Map接口及HashMap的底层实现

文章目录

1.Map接口2. HashMap3.LinkedHashMap4. Hashtable5. Properties6. TreeMap10.IdentityHashMap7. jdk7中HashMap底层原理实现（数组+链表）7.1 构造器7.2 put方法(添加)7.3 扩容 8. jdk8, HashMap的底层实现8.1 jdk7 与jdk8 中 HashMap的不同8.2 构造器8.3 Node 类型8.4 put8.5 resize 扩容 9. Map中定义的常用方法9.1 增，删，改操作9.2 元素查询9.3 元视图的操作(遍历key，value，以及key-vaule) 面试题

1.Map接口

---

Map接口是1.2才有

2. HashMap

---

作为Map的主要实现类，线程不安全，但是效率高。1.2才有。可以存储null的key和value。

在jdk7之前，使用的是数组+链表

jdk8之后，为了提高效率，使用数组+链表+红黑树实现。

3.LinkedHashMap

---

是HashMap的子类，在HashMap的基础上加了一对指针，指向前一个后一个元素，形成双向链表的结构。 这样在遍历的时候就效率就比较高。所以在经常遍历的情况下就选用LinkedHashMap，其他情况差不多都使用HashMap.

LinkedHashMap都没有重写HashMap的put方法，它重写的是在put方法中要用到的newNode。还有一个重要的区别就是LinkedHashMap的元素叫做Entry，是继承了HashMap的Node。

//LinkedHashMap中重写后的newNode Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<>(hash, key, value, e); linkNodeLast(p); return p; } //HashMap中的newNode Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } //LinkedHaspMap中的Entry static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }

4. Hashtable

---

作为Map的古老实现类，线程安全，但是效率低，设计上有缺陷。1.0就出现，比Map接口还要早，不能存储null的key和value，这一点就体现类Hashtable不够健壮。这个同vector一样，我们也不再使用他，虽然他是线程安全的。

5. Properties

---

Hashtable的子类，主要用来处理配置文件。key和value都是String类型。我们一般将配置文件(.properties)读入内存的时候就是用Properties这个数据结构来存储。

具体使用如下

// 这里io流的处理方法不严谨 public static void main(String[] args) throws Exception{ Properties prop = new Properties(); FileInputStream files = new FileInputStream("test.properties"); prop.load(files); // 将files对应的文件流加载到Properties对象中 String name = prop.getProperty("name"); String password = prop.getProperty("password"); System.out.println(name+password); files.close(); } // test.properties文件内容如下，该配置文件是在当前工程目录下 name=luca password=123

6. TreeMap

---

保证按照添加的Key-value对进行排序，但只会根据key排序，不会根据value排。所以一般都是key的自然排序和定制排序。因为有这个排序的特点，所以TreeMap的底层是用红黑二叉树实现。

虽然JDK8 后HashMap也是用红黑树实现的，但是HashMap要达到一定的条件后，才会将数组结构变为红黑树，有的场景需要你一开始就是排好序的，所以HashMap不能代替TreeMap

10.IdentityHashMap

在Java中，有一种key值可以重复的map，就是IdentityHashMap。在IdentityHashMap中，判断两个键值k1和 k2相等的条件是 k1 == k2 。在正常的Map 实现（如 HashMap）中，当且仅当满足下列条件时才认为两个键 k1 和 k2 相等：(k1null ? k2null : e1.equals(e2))。

IdentityHashMap类利用哈希表实现 Map 接口，比较键（和值）时使用引用相等性代替对象相等性。该类不是 通用 Map 实现！此类实现 Map 接口时，它有意违反 Map 的常规协定，该协定在比较对象时强制使用 equals 方法。此类设计仅用于其中需要引用相等性语义的罕见情况。

7. jdk7中HashMap底层原理实现（数组+链表）

7.1 构造器

---

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; threshold = initialCapacity; init(); } /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } /** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified <tt>Map</tt>. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); }

错的->//在实例化后，底层创建了长度为16的一维数组Entry [] table;

7.2 put方法(添加)

---

public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } 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; } /** * Inflates the table. */ private void inflateTable(int toSize) { // Find a power of 2 >= toSize int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); } static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }

首先会调用key1 所在类的hashCode()方法，计算key1的哈希值，此哈希值通过某种算法确定在Entry数组中的存放位置，

如果这个位置上的数据空，则直接添加进去.

如果这个位置数据不为空，这就意味着这个位置上有一个或多个数据，它们以链表的形式存在，这时就要将key1的哈希值与链表上所有key的哈希值比较。

如果key1的哈希值与链表上每一个key的哈希值都不相等，则添加进去。反之，调用key1所在类的equals()方法，

如果equals方法返回False，则说明不相等，添加进去

如果equals方法返回True，则说明相等，将value1替换掉原来的value。

7.3 扩容

---

/** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ 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); }

在不断的添加的过程中，会涉及到扩容的问题，当数组中的元素超出临界值（threshold）并且本次添加的位置为非空，则触发扩容。默认的扩容方式：扩容为原来的2倍，并将原有的数据复制过来。

临界值(threshold) = 数组容量*负载因子（loadfactor 默认为0.75）

8. jdk8, HashMap的底层实现

8.1 jdk7 与jdk8 中 HashMap的不同

---

jdk8 中的数组叫做 Node[], 而非Entry[]。其实它们两个区别不大。

jdk7的底层结构是：数组+链表，而jdk8的底层结构是：数组+链表+红黑树

当数组的某一个索引上的元素的数据（TREEIFY_THRESHOLD）（以链表形式存在）>8 且 当前数组长度(MIN_TREEIFY_CAPACITY)>64时，索引位置上的所有数据改为用红黑树存储。

8.2 构造器

---

/** * Constructs an empty {@code HashMap} with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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); } /** * Constructs an empty {@code HashMap} with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * Constructs an empty {@code HashMap} with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * Constructs a new {@code HashMap} with the same mappings as the * specified {@code Map}. The {@code HashMap} is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified {@code Map}. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

8.3 Node 类型

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

8.4 put

---

/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with {@code key}, or * {@code null} if there was no mapping for {@code key}. * (A {@code null} return can also indicate that the map * previously associated {@code null} with {@code key}.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods. * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }

8.5 resize 扩容

---

当刚初始化的时候，是不会创建数组的，在首次使用put的方法的时候，由于没有创建数组，就会进入resize，所以resize不仅是用来扩容的，在resize还负责来创建数组的功能.

扩容不是像ArrayList一样，不是等到HashMap已经装满才扩容。 HashMap是达到了一个临界值就会开始扩容。

临界值(threshold) = 数组容量*负载因子（loadfactor 默认为0.75，数组容量默认为16）。 这是因为HashMap与ArrayList不一样，ArrayList是按照顺序存的，但是HashMap不一样，它是按照哈希值来进行存储，所以会导致虽然这个数组中的元素已经很多了，但是还有一些Buckets却是空的。所以HashMap就设置了一个临界值，只要不是空的buckets的数量超过临界值就进行扩容。

/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

9. Map中定义的常用方法

9.1 增，删，改操作

---

V put(K key, V value)：将指定的key-value添加到(或修改)当前的map对象中

void putAll(map m)：将m中的key-vaule存到当前map中。

Object remove(Object key)：移除指定的key-vaule，并返回value。

void clear( )：清空当前map中所有的数据

9.2 元素查询

---

Object get(Object key)：获取指定key对应的value

boolean containsKey(Object key)：是否包含指定的key

boolean containsValue(Object value)：是否包含指定的value

int size( )：返回map中key-vaule的对数

boolean isEmpty()：判断当前map是否为空

boolean equals(Object obj)：判断当前map是否和参数对象obj是否相等。这个和Collection一样，只有obj也是个map，而且两个map里面的数据是一样的才会返回true。

9.3 元视图的操作(遍历key，value，以及key-vaule)

---

Map中是没有迭代器的，所以在遍历时，我们借助一些方法，将所有的vaule做成一个Set返回等等…

Set keySet()：返回所有key构成的Set集合；它是无序的，不可重复的，使用Set存储所有的key。这个Set的类型取决于Map的类型。（以HashMap为例）要求在key中的类要重写equals()和hashCode() 方法。

Collection vaules()：返回所有vaule构成的Collection集合。它是无序的，可重复的。使用Collection存储所有的value。 value所在的类要重写equals()方法。

Set entrySet()：返回所有key-vaule对构成的Set集合其实key-value是Entry对象的两个属性,Entry是无序的，不可重复的，使用Set来存储所有的Entry。

当然我们可以使用1,2 来实现3。

我们使用上面的方法后，就可以使用遍历Collection的方法来遍历Map了。

面试题

---

HashMap的底层实现原理

HashMap和Hashtable的异同

CurrentHashMap与HashMap的异同

这个时候再来。CurrentHashMap用于高并发的情况下。