Java Map接口详解

少年辛苦终身事,莫向光阴惰寸功。这篇文章主要讲述Java Map接口详解相关的知识,希望能为你提供帮助。


1、Map 概述

  1. Map与Collection并列存在。用于保存具有映射关系的数据:key-value
  2. Map 中的key 和value 都可以是任何引用类型的数据
  3. Map 中的key 用Set来存放,不允许重复,即同一个Map 对象所对应的类,须重写hashCode()和equals()方法
  4. 常用String类作为Map的“键”
  5. key 和value 之间存在单向一对一关系,即通过指定的key 总能找到唯一的、确定的value
  6. Map接口的常用实现类:HashMap、TreeMap、LinkedHashMap和Properties。
  7. HashMap是Map 接口使用频率最高的实现类
2、Map 常用方法
  • 添加、删除、修改操作:
  • Object put(Object key,Object value):将指定key-value添加到(或修改)当前map对象中
  • void putAll(Map m):将m中的所有key-value对存放到当前map中
  • Object remove(Object key):移除指定key的key-value对,并返回value
  • void clear():清空当前map中的所有数据
  • 元素查询的操作:
  • Object get(Object key):获取指定key对应的value
  • boolean containsKey(Object key):是否包含指定的key
  • boolean containsValue(Object value):是否包含指定的value
  • int size():返回map中key-value对的个数
  • boolean isEmpty():判断当前map是否为空
  • boolean equals(Object obj):判断当前map和参数对象obj是否相等
  • 元视图操作的方法:
  • Set keySet():返回所有key构成的Set集合
  • Collection values():返回所有value构成的Collection集合
  • Set entrySet():返回所有key-value对构成的Set集合
3、Map的实现类之一:HashMap
3.1 HashMap的存储结构
JDK 7及以前版本:HashMap是数组+链表结构(即为链地址法)
JDK 8版本发布以后:HashMap是数组+链表+红黑树实现。
JDK7:
Java Map接口详解

文章图片

JDK8:
Java Map接口详解

文章图片

3.2 HashMap概述Map中的key:无序的、不可重复的,使用Set存储所有的key。key所在的类要重写equals()和hashCode() (以HashMap为例)
Map中的value:无序的、可重复的,使用Collection存储所有的value。value所在的类要重写equals()
一个键值对:key-value构成了一个Entry对象。
Map中的entry:无序的、不可重复的,使用Set存储所有的entry
3.3 HashMap源码分析JDK7
public class HashMap< K,V>
extends AbstractMap< K,V>
implements Map< K,V> , Cloneable, Serializable


/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two < = 1< < 30.
*/
static final int MAXIMUM_CAPACITY = 1 < < 30;

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry< K,V> [] table;


/**
* The number of key-value mappings contained in this map.
*/
transient int size;

/**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
int threshold;

/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;


/**
* 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 an empty < tt> HashMap< /tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactorthe 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);
// initialCapacity:默认 16
// MAXIMUM_CAPACITY: 1< < 30
// 一般此处都跳过
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor < = 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);

// Find a power of 2 > = initialCapacity
int capacity = 1;
// 找一个 2的平方 > 初始化容量,就跳出
// capacity : 16
while (capacity < initialCapacity)
capacity < < = 1;

this.loadFactor = loadFactor;
// 临界值:16 * 0.75=12
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 创建数组
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() & &
(capacity > = Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();


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

/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 < < 4; // aka 16

/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two < = 1< < 30.
*/
static final int MAXIMUM_CAPACITY = 1 < < 30;

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;


/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
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 = https://www.songbingjia.com/android/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 = https://www.songbingjia.com/android/value;
value = https://www.songbingjia.com/android/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;




/**
* Constructs an empty < tt> HashMap< /tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactorthe 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 < 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.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted





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, dont 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;
// hashcode相等,key也相等,就覆盖原来数据
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;


// 1. key是null
// 2. hash值不等
// 3. hash值相等,key不等
if (e != null)// existing mapping for key
V oldValue = https://www.songbingjia.com/android/e.value;
if (!onlyIfAbsent || oldValue =https://www.songbingjia.com/android/= null)
e.value = https://www.songbingjia.com/android/value;
afterNodeAccess(e);
return oldValue;


++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;

【Java Map接口详解】3.4 HashMap的底层实现原理
  • jdk7说明:
  1. HashMap map = new HashMap()
  2. 在实例化以后,底层创建了长度是16的一维数组Entry[] table。
  3. 首先,调用key1所在类的hashCode()计算key1哈希值,此哈希值经过某种算法计算以后,得到在Entry数组中的存放位置。
  1. 如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功。情况2
  2. 如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同,继续比较:调用key1所在类的equals(key2)方法,比较:
  3. 如果equals()返回false:此时key1-value1添加成功。情况3
  4. 如果equals()返回true:使用value1替换value2。
  5. 如果此位置上的数据为空,此时的key1-value1添加成功。情况1
  6. 如果此位置上的数据不为空,(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值:
  7. 补充:关于情况2和情况3:此时key1-value1和原来的数据以链表的方式存储。
  1. 在不断的添加过程中,会涉及到扩容问题,当超出临界值(且要存放的位置非空)时,扩容。默认的扩容方式:扩容为原来容量的2倍,并将原有的数据复制过来。
  • jdk8 相较于jdk7在底层实现方面的不同:
  1. new HashMap():底层没有创建一个长度为16的数组
  2. jdk 8底层的数组是:Node[],而非Entry[]
  3. 首次调用put()方法时,底层创建长度为16的数组
  4. jdk7底层结构只有:数组+链表。jdk8中底层结构:数组+链表+红黑树。
  1. 形成链表时,七上八下(jdk7:新的元素指向旧的元素。jdk8:旧的元素指向新的元素)
  2. 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时,此时此索引位置上的所数据改为使用红黑树存储。
3.5 HashMap常用常量
  1. DEFAULT_INITIAL_CAPACITY : HashMap的默认容量,默认值:16
  2. MAXIMUM_CAPACITY :HashMap的最大支持容量,默认值:2^30
  3. DEFAULT_LOAD_FACTOR:HashMap的默认加载因子,默认值:0.75
  4. TREEIFY_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树,默认值:8
  5. UNTREEIFY_THRESHOLD:Bucket中红黑树存储的Node小于该默认值,转化为链表,默认值:6
  6. MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量。(当桶中Node的数量大到需要变红黑树时,若hash表容量小于MIN_TREEIFY_CAPACITY时,此时应执行resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。),默认值:64
  7. table:存储元素的数组,总是2的n次幂
  8. entrySet:存储具体元素的集
  9. size:HashMap中存储的键值对的数量
  10. modCount:HashMap扩容和结构改变的次数。
  11. threshold:扩容的临界值=容量*填充因子
  12. loadFactor:填充因子
3.6 HashMap什么时候进行扩容和树形化呢?当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时,就 会 进 行 数 组 扩 容 ,loadFactor的 默 认 值(DEFAULT_LOAD_FACTOR)为0.75,这是一个折中的取值。
默认情况下,数组大小(DEFAULT_INITIAL_CAPACITY)为16,那么当HashMap中元素个数超过160.75=12(这个值就是代码中的threshold值,也叫做临界值)的时候,就把数组的大小扩展为216=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
当HashMap中的其中一个链的对象个数如果达到了8个,此时如果capacity没有达到64,那么HashMap会先扩容解决,如果已经达到了64,那么这个链会变成树,结点类型由Node变成TreeNode类型。当然,如果当映射关系被移除后,下次resize方法时判断树的结点个数低于6个,也会把树再转为链表。
4、Map的实现类之二:HashMap的子类LinkedHashMap
  1. LinkedHashMap是HashMap的子类
  2. 在HashMap存储结构的基础上,使用了一对双向链表来记录添加元素的顺序
  3. 与LinkedHashSet类似,LinkedHashMap可以维护Map 的迭代顺序:迭代顺序与Key-Value 对的插入顺序一致
5、Map的实现类之三:TreeMap
  1. TreeMap存储Key-Value 对时,需要根据key-value 对进行排序。
  2. TreeMap可以保证所有的Key-Value 对处于有序状态。
  3. TreeSet底层使用红黑树结构存储数据
  4. TreeMap的Key 的排序:
  1. 自然排序:TreeMap的所有的Key 必须实现Comparable 接口,而且所有的Key 应该是同一个类的对象,否则将会抛出ClasssCastException
  2. 定制排序:创建TreeMap时,传入一个Comparator 对象,该对象负责对TreeMap中的所有key 进行排序。此时不需要Map 的Key 实现Comparable 接口
  1. TreeMap判断两个key相等的标准:两个key通过compareTo()方法或者compare()方法返回0。
6、Map的实现类之四:Hashtable
  1. Hashtable是个古老的Map 实现类,JDK1.0就提供了。
  2. 不同于HashMap,Hashtable是线程安全的。
  3. Hashtable实现原理和HashMap相同,功能相同。底层都使用哈希表结构,查询速度快,很多情况下可以互用。
  4. 与HashMap不同,Hashtable不允许使用null 作为key 和value
  5. 与HashMap一样,Hashtable也不能保证其中Key-Value 对的顺序
  6. Hashtable判断两个key相等、两个value相等的标准,与HashMap一致
7、Map的实现类之五:Hashtable的子类Properties
  1. Properties 类是Hashtable的子类,该对象用于处理属性文件
  2. 由于属性文件里的key、value 都是字符串类型,所以Properties 里的key 和value 都是字符串类型
  3. 存取数据时,建议使用setProperty(String key,Stringvalue)方法和getProperty(String key)方法



    推荐阅读