Map集合

Map接口

概述

• Map集合从何而来

• 我们通过什么东西来标识我们的学生在班级的唯一性. 我们都每一个学生应该存在一个学号 , 而这个学号是唯一的。那么我们就可以通过这个学号来表示我们学生在班级的唯一性。那么也就说,我们的学号和学生的姓名之间应该存在一个对应关系吧

• 那么我们怎么存储这样对应关系的数据呢? 针对这个情况java就给我们提供了另外一种集合进行表示,而这个集合就是Map 。Map集合结构是由两列组成,第一列被称之为键 , 第二例被称之为值 ; 并且我们都知道键应该是唯一的,而对值没有要求。

• Map接口和Collection接口的区别

  • Map是双列的,Collection是单列的
  • Map的键唯一,Collection的子体系Set是唯一的
  • Map集合的数据结构值针对键有效，跟值无关
  • Collection集合的数据结构是针对元素有效

• Map集合的特点

  • 将键映射到值的对象
  • 一个映射不能包含重复的键
  • 每个键最多只能映射到一个值

Map集合整体结构

• HashMap 等其他 Map 实现则是都扩展了AbstractMap，里面包含了通用方法抽象。不同 Map的用途，从类图结构就能体现出来，设计目的已经体现在不同接口上。
• Hashtable 比较特别，作为类似 Vector、Stack 的早期集合相关类型，它是扩展了 Dictionary 类的，类结构上与 HashMap 之类明显不同。
• 大部分使用 Map 的场景，通常就是放入、访问或者删除，而对顺序没有特别要求，HashMap 在这种情况下基本是最好的选择。HashMap的性能表现非常依赖于哈希码的有效性，请务必掌握hashCode 和 equals 的一些基本约定，比如：
  • equals 相等，hashCode 一定要相等。
  • 重写了 hashCode 也要重写 equals。
  • hashCode 需要保持一致性，状态改变返回的哈希值仍然要一致。
  • equals 的对称、反射、传递等特性。

功能概述

1:添加功能
    V put(K key,V value):添加元素。
    如果键是第一次存储，就直接存储元素，返回null
    如果键不是第一次存在，就用值把以前的值替换掉，返回以前的值
2:删除功能
	void clear():移除所有的键值对元素
	V remove(Object key)：根据键删除键值对元素，并把值返回
3:判断功能
	boolean containsKey(Object key)：判断集合是否包含指定的键
	boolean containsValue(Object value):判断集合是否包含指定的值
	boolean isEmpty()：判断集合是否为空
4:获取功能
	Set<Map.Entry<K,V>> entrySet():返回的是键值对对象的集合
	V get(Object key):根据键获取值
	Set<K> keySet():获取集合中所有键的集合
	Collection<V> values():获取集合中所有值的集合
5：长度功能
	int size()：返回集合中的键值对的对数

• 示例代码

  // 创建集合对象
  Map<String, String> map = new HashMap<String, String>();
  
  //添加元素
  System.out.println("put:" + map.put("0001", "麓殇"));		//put:null
  System.out.println("put:" + map.put("0001", "旧青画"));		//put:麓殇
  System.out.println("put:" + map.put("0002", "蓝奕世"));		// put:null
  System.out.println("put:" + map.put("0003", "不可言"));		// put:null
  System.out.println("put:" + map.put("0004", "苏莫晨"));		// put:null
  
  //void clear():移除所有的键值对元素
  map.clear();
  System.out.println("size:"+map.size());		//size:0
  
  System.out.println("remove:" + map.remove("0001"));	//remove:旧青画
  System.out.println("remove:" + map.remove("0005"));	//remove:null
  System.out.println("map:" + map);		//map:{0004=苏莫晨, 0002=蓝奕世, 0003=不可言}
  
  System.out.println("isEmpty:"+map.isEmpty());		//isEmpty:false
  
  System.out.println("containsKey:" + map.containsKey("0004"));	//containsKey:true
  System.out.println("containsKey:" + map.containsKey("0005"));	//containsKey:false
  
  // 获取功能
  // V get(Object key):根据键获取值
  System.out.println("get:" + map.get("0001"));	//旧青画
  System.out.println("get:" + map.get("周杰")); 	// 返回null
  
  // Set<K> keySet():获取集合中所有键的集合
  Set<String> set = map.keySet();
  for (String key : set) {
  	System.out.println(key);
  }
  结果:
  	0004
  	0002
  	0003
  	0001
  
  // Collection<V> values():获取集合中所有值的集合
  Collection<String> con = map.values();
  for (String value : con) {
  	System.out.println(value);
  }
  结果:
  	苏莫晨
  	蓝奕世
  	不可言
  	旧青画

Map集合遍历

根据键找值

• 1: 获取所有的键对应的Set集合 ；2: 遍历Set获取每一个键 , 根据键找出对应的值

思路：
	A:把所有的丈夫给集中起来。
	B:遍历丈夫的集合，获取得到每一个丈夫。
	C:让丈夫去找自己的妻子。
转换：
	A:获取所有的键 keySet()
	B:遍历键的集合，获取得到每一个键
	C:根据键去找值

• 示例

  // 创建集合对象
  		Map<String, String> map = new HashMap<String, String>();
  
  		// 创建元素并添加到集合
  		map.put("杨过", "小龙女");
  		map.put("郭靖", "黄蓉");
  		map.put("杨康", "穆念慈");
  		map.put("陈玄风", "梅超风");
  
  		// 遍历
  		// 获取所有的键
  		Set<String> set = map.keySet();
  		// 遍历键的集合，获取得到每一个键
  		for (String key : set) {
  			// 根据键去找值
  			String value = map.get(key);
  			System.out.println(key + "---" + value);
  		}
  	}

遍历根据键值对对象

• 遍历键值对对象，根据键值对对象获取键和值

  思路：
  	A:获取所有结婚证的集合
  	B:遍历结婚证的集合，得到每一个结婚证
  	C:根据结婚证获取丈夫和妻子
  
  转换：
  	A:获取所有键值对对象的Set集合 Set<Map.Entry<K,V>> entrySet()
  	B:遍历键值对对象的集合，得到每一个键值对对象
  	C:根据键值对对象获取键和值

• 示例代码

  // 创建集合对象
  Map<String, String> map = new HashMap<String, String>();
  
  // 创建元素并添加到集合
  map.put("杨过", "小龙女");
  map.put("郭靖", "黄蓉");
  map.put("杨康", "穆念慈");
  map.put("陈玄风", "梅超风");
  
  // 获取所有键值对对象的集合
  Set<Map.Entry<String, String>> set = map.entrySet();
  // 遍历键值对对象的集合，得到每一个键值对对象
  for (Map.Entry<String, String> me : set) {
  	// 根据键值对对象获取键和值
  	String key = me.getKey();
  	String value = me.getValue();
  	System.out.println(key + "---" + value);
  }

迭代器

• 代码如下：

  //第二种方式，使用迭代器
  Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
  while (iterator.hasNext()){
      Map.Entry<String, Integer> next = iterator.next();
      String key = next.getKey();
      Integer value = next.getValue();
      System.out.println(key + ": " + value);
  }
  while (iterator.hasNext()){
      Map.Entry<String, Integer> next = iterator.next();
      String key = next.getKey();
      //通过key找键，效率相比比较低
      Integer value = map.get(key);
      System.out.println(key + ": " + value);
  }

HashMap

特点

• Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it isunsynchronizedandpermits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

• 键是哈希表结构，可以保证键的唯一性

• 基于Map接口实现、允许null键/值、是非同步(这点很重要，多线程注意)、不保证有序(比如插入的顺序)、也不保证序不随时间变化。

  • 允许插入最多一条key为null的记录，允许插入多条value为null的记录。

  • HashMap 不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此在不同时间段迭代同一个 HashMap 的顺序可能会不同。

  • HashMap 非线程安全，即任一时刻有多个线程同时写 HashMap 的话可能会导致数据的不一致

HashMap<String,String>

• 需求: 使用HashMap存储元素,键是String类型, 值也是String类型

// 创建集合对象
HashMap<String, String> hm = new HashMap<String, String>();

// 创建元素并添加元素
// String key1 = "001";
// String value1 = "欧展鹏";

hm.put("001", "欧展鹏");
hm.put("002", "嘉澜");
hm.put("002", "嘉澜");
hm.put("003", "丘黎");
hm.put("004", "如空月");
hm.put("005", "言思晴");
hm.put("001", "东方不败");

// 遍历
Set<String> set = hm.keySet();
for (String key : set) {
	String value = hm.get(key);
	System.out.println(key + "---" + value);
}
结果:
	001---欧展鹏
	002---嘉澜
	003---丘黎
	004---如空月
	005---东方不败

HashMap<Integer,String>

• 使用HashMap存储元素,键是String类型 ,值是Student类型

// 创建集合对象
HashMap<Integer, String> hm = new HashMap<Integer, String>();

// 创建元素并添加元素
// Integer i = new Integer(27);
// Integer i = 27;
// String s = "欧展鹏";
// hm.put(i, s);

hm.put(27, "欧展鹏");
hm.put(30, "丘黎");
hm.put(28, "如空月");
hm.put(29, "嘉澜");

// 下面的写法是八进制，但是不能出现8以上的单个数据
// hm.put(003, "hello");
// hm.put(006, "hello");
// hm.put(007, "hello");
// hm.put(008, "hello");

// 遍历:获取所有的键值对对象对应的Set集合
Set<Integer> set = hm.keySet();
for (Integer key : set) {
	String value = hm.get(key);
	System.out.println(key + "---" + value);
}

// 下面这种方式仅仅是集合的元素的字符串表示
// System.out.println("hm:" + hm);
}
结果:
	27---欧展鹏
	28---如空月
	29---嘉澜
	30---丘黎

HashMap<String,Student>

• 使用HashMap存储元素,键是String类型 ,值是Student类型

// 创建集合对象
HashMap<String, Student> hm = new HashMap<String, Student>();

// 创建学生对象
Student s1 = new Student("欧展鹏", 58);
Student s2 = new Student("如空月", 55);
Student s3 = new Student("迦南", 54);
Student s4 = new Student("球溪", 50);

// 添加元素
hm.put("9527", s1);
hm.put("9522", s2);
hm.put("9524", s3);
hm.put("9529", s4);

// 遍历
Set<String> set = hm.keySet();
for (String key : set) {
	// 注意了：这次值不是字符串了
	// String value = hm.get(key);
	Student value = hm.get(key);
	System.out.println(key + "---" + value.getName() + "---"
			+ value.getAge());
}
结果:
	9524---迦南---54
	9522---如空月---55
	9529---球溪---50
	9527---欧展鹏---58

HashMap<Student,String>

• 使用HashMap存储元素,键是Student类型 , 值是String类型
• 如果两个对象的成员变量值是相同的,那么我们认为就是同一个对象,如果是同一个对象就不能添加到HashMap集合中

// 创建集合对象
HashMap<Student, String> hm = new HashMap<Student, String>();

// 创建学生对象
Student s1 = new Student("貂蝉", 27);
Student s2 = new Student("王昭君", 30);
Student s3 = new Student("西施", 33);
Student s4 = new Student("杨玉环", 35);
Student s5 = new Student("貂蝉", 27);

// 添加元素
hm.put(s1, "8888");
hm.put(s2, "6666");
hm.put(s3, "5555");
hm.put(s4, "7777");
hm.put(s5, "9999");

// 遍历
Set<Student> set = hm.keySet();
for (Student key : set) {
	String value = hm.get(key);
	System.out.println(key.getName() + "---" + key.getAge() + "---"
			+ value);
}

//要求：如果两个对象的成员变量值都相同，则为同一个对象。
//哈希表作用是用来保证键的唯一性的。
//需要重写hashCode()和equals()方法

结果:
	王昭君---30---6666
	貂蝉---27---9999
	杨玉环---35---7777
	西施---33---5555

HashMap原理

• HashMap基于哈希思想，实现对数据的读写。
  • put存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。
  • get获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。
• HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。
  • 如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

HashMap内部结构

• HashMap 内部的结构，它可以看作是数组（Node[] table）和链表结合组成的复合结构，数组被分为一个个桶（bucket），通过哈希值决定了键值对在这个数组的寻址；哈希值相同的键值对，则以链表形式存储，你可以参考下面的示意图。

  

• 这里需要注意的是，如果链表大小超过阈值（TREEIFY_THRESHOLD, 8，图中的链表就会被改造为树形结构。

HashMap底层实现

• 底层是用什么实现的？
  • HashMap 实际上是数组+链表+红黑树的结合体……
• 为什么要使用链表？
  • 当发生碰撞了，对象将会储存在链表的下一个节点中
• 为什么要使用红黑树？
  • JDK1.8 开始 HashMap 通过使用红黑树来提高元素查找效率

HashMap构造函数

• HashMap构造函数如下所示

  • 默认装载因子0.75
  • 数组的扩容临界点：当前容量 x 装载因子

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

成员变量

• 成员变量如下所示

  //哈希桶数组，在第一次使用时才初始化
  //容量值应是2的整数倍
  transient Node<K, V>[] table;
  
  /**
   * Holds cached entrySet(). Note that AbstractMap fields are used
   * for keySet() and values().
   */
  transient Set<Map.Entry<K, V>> entrySet;
  
  //Map的大小
  transient int size;
  
  //每当Map的结构发生变化时，此参数就会递增
  //当在对Map进行迭代操作时，迭代器会检查此参数值
  //如果检查到此参数的值发生变化，就说明在迭代的过程中Map的结构发生了变化，因此会直接抛出异常
  transient int modCount;
  
  //数组的扩容临界点，当数组的数据量达到这个值时就会进行扩容操作
  //计算方法：当前容量 x 装载因子
  int threshold;
  
  //使用的装载因子值
  final float loadFactor;

put(K key, V value)

• put函数大致的思路为：

  1. 对key的hashCode()做hash，然后再计算index;
     • putVal()方法的部分源码，可以看出，向集合中添加元素时，会使用(n - 1) & hash的计算方法来得出该元素在集合中的位置
     • 其中n是集合的容量，hash是添加的元素进过hash函数计算出来的hash值。
  2. 如果没碰撞直接放到bucket里；
  3. 如果碰撞了，以链表的形式存在buckets后；
  4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD(树阈))，就把链表转换成红黑树；
  5. 如果节点已经存在就替换old value(保证key的唯一性)
  6. 如果bucket满了(超过load factor*current capacity)，就要resize。

• put源码如下所示

  public V put(K key, V value) {
      // 对key的hashCode()做hash
      return putVal(hash(key), key, value, false, true);
  }
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
      Node<K,V>[] tab; Node<K,V> p; int n, i;
      // tab为空则创建
      if ((tab = table) == null || (n = tab.length) == 0)
          n = (tab = resize()).length;
      // 计算index，并对null做处理
      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;
      // 超过load factor*current capacity，resize
      if (++size > threshold)
          resize();
      afterNodeInsertion(evict);
      return null;
  }

• put源码解析大概如下所示

  • 如果表格是 null，resize 方法会负责初始化它，这从 tab = resize() 可以看出。
  • resize 方法兼顾两个职责，创建初始存储表格，或者在容量不满足需求的时候，进行扩容（resize）。
  • 在放置新的键值对的过程中，如果发生if (++size > threshold)条件，就会发生扩容。
  • 具体键值对在哈希表中的位置（数组 index）取决于下面的位运算：i = (n - 1) & hash
  • 仔细观察哈希值的源头，我们会发现，它并不是 key 本身的hashCode，而是来自于 HashMap 内部的另外一个 hash 方法。注意，为什么这里需要将高位数据移位到低位进行异或运算呢？这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞。

• 当有键值对插入时，HashMap会发生什么 ?

  • 首先，键的哈希值被计算出来，然后这个值会赋给 Entry 类中对应的 hashCode 变量。
  • 然后，使用这个哈希值找到它将要被存入的数组中“桶”的索引。
  • 如果该位置的“桶”中已经有一个元素，那么新的元素会被插入到“桶”的头部，next 指向上一个元素——本质上使“桶”形成链表。

get(Object key)

• 在理解了put之后，get就很简单了。大致思路如下：

• 具体代码的实现如下：

  public V get(Object key) {
      Node<K,V> e;
      return (e = getNode(hash(key), key)) == null ? null : e.value;
  }
  final Node<K,V> getNode(int hash, Object key) {
      Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
      if ((tab = table) != null && (n = tab.length) > 0 &&
          (first = tab[(n - 1) & hash]) != null) {
          // 直接命中
          if (first.hash == hash && // always check first node
              ((k = first.key) == key || (key != null && key.equals(k))))
              return first;
          // 未命中
          if ((e = first.next) != null) {
              // 在树中get
              if (first instanceof TreeNode)
                  return ((TreeNode<K,V>)first).getTreeNode(hash, key);
              // 在链表中get
              do {
                  if (e.hash == hash &&
                      ((k = e.key) == key || (key != null && key.equals(k))))
                      return e;
              } while ((e = e.next) != null);
          }
      }
      return null;
  }

• 大概的意思是

  • bucket里的第一个节点，直接命中；
  • 如果有冲突，则通过key.equals(k)去查找对应的entry
    • 若为树，则在树中通过key.equals(k)查找，O(logn)；
    • 若为链表，则在链表中通过key.equals(k)查找，O(n)。

• 对于查找一个key时，HashMap会发生什么 ?

  • 键的哈希值先被计算出来
  • 在 mHashes[] 数组中二分查找此哈希值。这表明查找的时间复杂度增加到了 O(logN)。
  • 一旦得到了哈希值所对应的索引 index，键值对中的键就存储在 mArray[2index] ，值存储在 mArray[2index+1]。
  • 这里的时间复杂度从 O(1) 上升到 O(logN)，但是内存效率提升了。当我们在 100 左右的数据量范围内尝试时，没有耗时的问题，察觉不到时间上的差异，但我们应用的内存效率获得了提高。

remove(Object key)

• 从 Map 中移除键值对的操作，在底层数据结构的体现就是移除对某个结点对象的引用，可能是从数组中、也可能是链表或者红黑树。

  public V remove(Object key) {
      Node<K, V> e;
      return (e = removeNode(hash(key), key, null, false, true)) == null ?
              null : e.value;
  }
  
  /**
   * Implements Map.remove and related methods
   *
   * @param hash       key 的哈希值
   * @param key        the key
   * @param value      key对应的值，只有当 matchValue 为 true 时才需要使用到，否则忽略该值
   * @param matchValue 如果为 true ，则只有当 Map 中存在某个键 equals key 且 value 相等时才会移除该元素，否则只要 key 的 hash 值相等就直接移除该元素
   * @param movable    if false do not move other nodes while removing
   * @return the node, or null if none
   */
  final Node<K, V> removeNode(int hash, Object key, Object value,
                              boolean matchValue, boolean movable) {
      Node<K, V>[] tab;
      Node<K, V> p;
      int n, index;
      //只有当 table 不为空且 hash 对应的索引位置存在值时才有可移除的对象
      if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
          Node<K, V> node = null, e;
          K k;
          V v;
          //如果与头结点的 key 相等
          if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
              node = p;
          else if ((e = p.next) != null) { //存在哈希冲突
              //用红黑树来处理哈希冲突
              if (p instanceof TreeNode)
                  //查找对应结点
                  node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
              else { //用链表来处理哈希冲突
                  do {
                      if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                          node = e;
                          break;
                      }
                      p = e;
                  } while ((e = e.next) != null);
              }
          }
          //node != null 说明存在相应结点
          //如果 matchValue 为 false ，则通过之前的判断可知查找到的结点的 key 与 参数 key 的哈希值一定相等，此处就可以直接移除结点 node
          //如果 matchValue 为 true ，则当 value 相等时才需要移除该结点
          if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
              if (node instanceof TreeNode) //对应红黑树
                  ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
              else if (node == p) //对应 key 与头结点相等的情况，此时直接将指针移向下一位即可
                  tab[index] = node.next;
              else //对应的是链表的情况
                  p.next = node.next;
              ++modCount;
              --size;
              //用于 LinkedHashMap ，在 HashMap 中是空实现
              afterNodeRemoval(node);
              return node;
          }
      }
      return null;
  }

resize()扩容

• 初始化或加倍表大小。

  • 如果为NULL，则按照在字段阈值中保持的初始容量目标分配。否则，由于我们使用的是二次幂展开，每个bin中的元素要么保持在相同的索引中，要么在新表中以两个偏移的幂移动。

• 依据 resize 源码，不考虑极端情况（容量理论最大极限由MAXIMUM_CAPACITY 指定，数值为1<<30，也就是 2 的 30 次方），可以归纳为：

  • 门限值等于（负载因子）x（容量），如果构建 HashMap的时候没有指定它们，那么就是依据相应的默认常量值。
  • 门限通常是以倍数进行调整 （newThr = oldThr << 1），我前面提到，根据 putVal 的逻辑，当元素个数超过门限大小时，则调整 Map 大小。
  • 扩容后，需要将老的数组中的元素重新放置到新的数组，这是扩容的一个主要开销来源。

• HashMap的容量为什么是2的n次幂，和put的计算index方法((n - 1) & hash)有着千丝万缕的关系，

• 符号&是按位与的计算，这是位运算，计算机能直接运算，特别高效，

• 按位与&的计算方法是，只有当对应位置的数据都为1时，运算结果也为1，

• 当HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞，下面举例进行说明。

• HashMap的容量是16时，它的二进制是10000，(n-1)的二进制是01111，与hash值得计算结果如下：

  • 不同的hash值，和(n-1)进行位运算后，能够得出不同的值，使得添加的元素能够均匀分布在集合中不同的位置上，避免hash碰撞。
  • HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，是因为容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！

• resize()源码如下所示

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

• 当put时，如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例，那么就会发生resize。

  • 在resize的过程，简单的说就是把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中。resize的注释是这样描述的：

  • 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 eitherstay at same index, ormove with a power of two offsetin the new table.

  • 大致意思就是说，当超过限制的时候会resize，然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

• 例如我们从16扩展为32时，(n - 1) & hash表示计算元素在集合的位置具体的变化如下所示：

  • 长度为16的时候，n-1=15=1111

    • hash1和hash2 与运算后的结果都为0101

  • 扩容后32，n-1: 31=11111

    • hash1与运算后的结果都为0101
    • hsh2 与运算后的结果都为10101

  • 

  • 因此扩容后，那么n-1的mask范围在高位多1bit(红色)，因此新的index计算就会发生这样的变化：

  • 

  • 因此，我们在扩充HashMap的时候，不用重新计算hash值。只需要看看(hash&n-1)值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：

  • 

  • 这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

Hash函数实现

• 首先看下存储put代码

  public V put(K key, V value) {
      return putVal(hash(key), key, value, false, true);
  }
  
  
  static final int hash(Object key) {
      int h;
      //高位运算
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

• 可以看到这个函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或。其中代码注释是这样写的：

  /**
   * Computes key.hashCode() and spreads (XORs) higher bits of hash
   * to lower.  Because the table uses power-of-two masking, sets of
   * hashes that vary only in bits above the current mask will
   * always collide. (Among known examples are sets of Float keys
   * holding consecutive whole numbers in small tables.)  So we
   * apply a transform that spreads the impact of higher bits
   * downward. There is a tradeoff between speed, utility, and
   * quality of bit-spreading. Because many common sets of hashes
   * are already reasonably distributed (so don't benefit from
   * spreading), and because we use trees to handle large sets of
   * collisions in bins, we just XOR some shifted bits in the
   * cheapest possible way to reduce systematic lossage, as well as
   * to incorporate impact of the highest bits that would otherwise
   * never be used in index calculations because of table bounds.
   */

• 在get和put的过程中，计算下标时，先对hashCode进行hash操作，然后再通过hash值进一步计算下标，如下图所示：

  • 

• 在设计hash函数时，因为目前的table长度n为2的幂，而计算下标的时候，是这样实现的(使用&位操作，而非%求余)：

  (n - 1) & hash

• 设计者认为这方法很容易发生碰撞。为什么这么说呢？

  • 不妨思考一下，在n - 1为15(0x1111)时，其实散列真正生效的只是低4bit的有效位，当然容易碰撞了。
  • 因此，设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

• 如果还是产生了频繁的碰撞，会发生什么问题呢？

  • 作者注释说，他们使用树来处理频繁的碰撞(we use trees to handle large sets of collisions in bins)，在JEP-180中，描述了这个问题：

  • Improve the performance of java.util.HashMap under high hash-collision conditions byusing balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.

• 之前已经提过，在获取HashMap的元素时，基本分两步：

  • 1.首先根据hashCode()做hash，然后确定bucket的index；
  • 2.如果bucket的节点的key不是我们需要的，则通过keys.equals()在链中找。

• 在Java 8之前的实现中是用链表解决冲突的

  • 在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。
  • 因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题。

• 为什么要这样实现hash？

  • 在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

容量和装载因子

• 在HashMap中有两个很重要的参数，容量(Capacity)和负载因子(Load factor)

  • 简单的说，Capacity就是bucket的大小，Loadfactor就是bucket填满程度的最大比例。
  • 如果对迭代性能要求很高的话，不要把capacity设置过大，也不要把load factor设置过小。
  • 当bucket中的entries的数目大于capacity*load factor时就需要调整bucket的大小为当前的2倍。

• 什么是装载因子

  • 装载因子用于规定数组在自动扩容之前可以数据占有其容量的最高比例，即当数据量占有数组的容量达到这个比例后，数组将自动扩容。
  • 装载因子衡量的是一个散列表的空间的使用程度，装载因子越大表示散列表的装填程度越高，反之愈小。因此如果装载因子越大，则对空间的利用程度更高，相对应的是查找效率的降低。
  • 如果装载因子太小，那么数组的数据将过于稀疏，对空间的利用率低，官方默认的装载因子为0.75，是平衡空间利用率和运行效率两者之后的结果。
  • 如果在实际情况中，内存空间较多而对时间效率要求很高，可以选择降低装载因子的值；如果内存空间紧张而对时间效率要求不高，则可以选择提高装载因子的值。
  • 此外，即使装载因子和哈希算法设计得再合理，也不免会出现由于哈希冲突导致链表长度过长的情况，这将严重影响 HashMap 的性能。为了优化性能，从 JDK1.8 开始引入了红黑树，当链表长度超出 TREEIFY_THRESHOLD 规定的值时，链表就会被转换为红黑树，利用红黑树快速增删改查的特点以提高 HashMap 的性能。

  //序列化ID
  private static final long serialVersionUID = 362498820763181265L;
  
  //哈希桶数组的默认容量
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  
  //网上很多文章都说这个值是哈希桶数组能够达到的最大容量，其实这样说并不准确
  //从 resize() 方法的扩容机制可以看出来，HashMap 每次扩容都是将数组的现有容量增大一倍
  //如果现有容量已大于或等于 MAXIMUM_CAPACITY ，则不允许再次扩容
  //否则即使此次扩容会导致容量超出 MAXIMUM_CAPACITY ，那也是允许的
  static final int MAXIMUM_CAPACITY = 1 << 30;
  
  //装载因子的默认值
  //装载因子用于规定数组在自动扩容之前可以数据占有其容量的最高比例，即当数据量占有数组的容量达到这个比例后，数组将自动扩容
  //装载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小
  //对于使用链表的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，则对空间的利用程度更高，相对应的是查找效率的降低
  //如果负载因子太小，那么数组的数据将过于稀疏，对空间的利用率低
  //官方默认的负载因子为0.75，是平衡空间利用率和运行效率两者之后的结果
  static final float DEFAULT_LOAD_FACTOR = 0.75f;
  
  //为了提高效率，当链表的长度超出这个值时，就将链表转换为红黑树
  static final int TREEIFY_THRESHOLD = 8;

• HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

  • 如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。

hashCode和equal

• get和put的中的equals()和hashCode()的都有什么作用？
  • 通过对key的hashCode()进行hashing，并计算下标( (n-1) & hash)，从而获得buckets的位置。
  • 如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点

HashMap的table下标

• 它是用自己的hash方法确定下标
  • HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；
  • 在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；
• 不直接使用hashCode()处理后的哈希值
  • hashCode()方法返回的是int整数类型，其范围为-(2^31)(2^31-1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
• 为什么数组长度要保证为2的幂次方呢？
  • 只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，即实现了key的定位，2的幂次方也可以减少冲突次数，提高HashMap的查询效率；
  • 如果 length 为 2 的次幂 则 length-1 转化为二进制必定是 11111……的形式，在于 h 的二进制与操作效率会非常的快，而且空间不浪费；如果 length 不是 2 的次幂，比如 length 为 15，则 length - 1 为 14，对应的二进制为 1110，在于 h 与操作，最后一位都为 0 ，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

Key为何需要不可变

• 为什么HashMap中String、Integer这样的包装类适合作为K？
  • String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率
    • 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
    • 内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况
    • 如果对象在创建后它的哈希值发生了变化，则Map对象很可能就定位不到映射的位置。
• 想要让自己的Object作为K应该怎么办呢？
  • 重写hashCode()和equals()方法
    • 重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；
    • 重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性；
• 总结
  • 采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获

HashMap为啥要扩容

• HashMap是为啥要扩容
  • 当链表数组的容量超过初始容量*加载因子（默认0.75）时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中。为什么需要使用加载因子？为什么需要扩容呢？因为如果填充比很大，说明利用的空间很多，如果一直不进行扩容的话，链表就会越来越长，这样查找的效率很低，扩容之后，将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率。

HashMap扩容存在问题

• hashmap不能用于多线程场景中，并发环境下，需要扩容时候出现循环链表，通过get获取值造成死循环。多线程下推荐使用concurrentHashmap！

• 当多线程的情况下，可能产生条件竞争。当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来(jdk7 将遍历到的节点放入到链表头)，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。

• jdk1.7及以前 扩容时使用的头插法 并发时可能会形成环状链表造成死循环

• 1.8改为了尾插法 可以避免这种问题 只是依然避免不了节点丢失的问题

• 简单说:扩容过程中使用头插法将oldTable中的单链表中的节点插入到newTable的单链表头中，所以newTable中的单链表会倒置oldTable中的单链表。那么在多个线程同时扩容的情况下就可能导致扩容后的HashMap中存在一个有环的单链表，从而导致后续执行get操作的时候，会触发死循环，引起CPU的100%问题。所以一定要避免在并发环境下使用HashMap。

• JDK1.7复制表

  void resize(int newCapacity)
  {
      Entry[] oldTable = table;
      int oldCapacity = oldTable.length;
      ......
      //创建一个新的Hash Table
      Entry[] newTable = new Entry[newCapacity];
      //将Old Hash Table上的数据迁移到New Hash Table上
      transfer(newTable);
      table = newTable;
      threshold = (int)(newCapacity * loadFactor);
  }
  
  //重点在这里面的transfer()!
  void transfer(Entry[] newTable)
  {
      Entry[] src = table;
      int newCapacity = newTable.length;
      //下面这段代码的意思是：
      //  从OldTable里摘一个元素出来，然后放到NewTable中
      for (int j = 0; j < src.length; j++) {
          Entry<K,V> e = src[j];
          if (e != null) {
              src[j] = null;
              do {
                  Entry<K,V> next = e.next;
                  int i = indexFor(e.hash, newCapacity);
                  e.next = newTable[i];
                  newTable[i] = e;
                  e = next;
              } while (e != null);
          }
      }
  }

• 正常扩容

  • 倒置了key7 在 key3 前面了

  

• 并发下二个线程进行扩容

  • 线程1执行到Entry<K,V> next = e.next;后挂起，e指向元素3，e.next指向元素7
  • 线程2在new table的数组3位置依次用头插法插入3个元素后如下图所示

  

  • 线程2扩容完毕，线程1开始扩容，此时线程B继续执行以下代码

    Entry<K,V> next = e.next;   //e=key3，next=key7
    // 头插法，将key3放到数组3都头部
    e.next = newTable[i];    //将数组3的地址赋予变量e.next
    newTable[i] = e; //将3放到数组3的位置
    e = next;　　//  e = next = key7

    • 

• e != null 继续执行,这里由于线程2的扩容导致链表倒置，这里会在扩容后出现环。

  // 线程2导致了key7的next变成了key3
  Entry<K,V> next = e.next;  //  e=key7,next = key3
  e.next = newTable[i];　// key7的下一个指向数组3的位置
  newTable[i] = e; //将key7放到数组3的位置
  e = next;　　　　//e =next = key3

  

• 1.8后采用尾插法，可以避免这种问题 只是依然避免不了节点丢失的问题，如果最后用thead1的结果作为扩容结果，key5的节点就丢失了

• 1.8后的链表可能转换成树，可能会产生红黑树成环的场景导致死循环。

HashMap线程问题

• HashMap是非线程安全的，那么测试一下，先看下测试代码

  private HashMap map = new HashMap();
  private void test(){
      Thread t1 = new Thread() {
          @Override
          public void run() {
              for (int i = 0; i < 100; i++) {
                  map.put(new Integer(i), i);
              }
              LogUtils.d("yc-----执行结束----t1");
          }
      };
  
      Thread t2 = new Thread() {
          @Override
          public void run() {
              for (int i = 0; i < 100; i++) {
                  map.put(new Integer(i), i);
              }
              LogUtils.d("yc-----执行结束----t2");
          }
      };
  
      Thread t3 = new Thread() {
          @Override
          public void run() {
              for (int i = 0; i < 100; i++) {
                  map.put(new Integer(i), i);
              }
              LogUtils.d("yc-----执行结束----t2");
          }
      };
  
      Thread t4 = new Thread() {
          @Override
          public void run() {
              for (int i = 0; i < 100; i++) {
                  map.get(new Integer(i));
              }
              LogUtils.d("yc-----执行结束----t2");
          }
      };
  
      Thread t5 = new Thread() {
          @Override
          public void run() {
              for (int i = 0; i < 100; i++) {
                  map.get(new Integer(i));
              }
              LogUtils.d("yc-----执行结束----t2");
          }
      };
  
      Thread t6 = new Thread() {
          @Override
          public void run() {
              for (int i = 0; i < 100; i++) {
                  map.get(new Integer(i));
              }
              LogUtils.d("yc-----执行结束----t2");
          }
      };
  
  
      t1.start();
      t2.start();
      t3.start();
      t4.start();
      t5.start();
      t6.start();
  }

• 就是启了6个线程，不断的往一个非线程安全的HashMap中put/get内容，put的内容很简单，key和value都是从0自增的整数（这个put的内容做的并不好，以致于后来干扰了我分析问题的思路）。对HashMap做并发写操作，我原以为只不过会产生脏数据的情况，但反复运行这个程序，会出现线程t1、t2被卡住的情况，多数情况下是一个线程被卡住另一个成功结束，偶尔会6个线程都被卡住。

  • 多线程下直接使用ConcurrentHashMap，解决了这个问题。
  • CPU利用率过高一般是因为出现了出现了死循环，导致部分线程一直运行，占用cpu时间。问题原因就是HashMap是非线程安全的，多个线程put的时候造成了某个key值Entry key List的死循环，问题就这么产生了。
  • 当另外一个线程get 这个Entry List 死循环的key的时候，这个get也会一直执行。最后结果是越来越多的线程死循环，最后导致卡住。我们一般认为HashMap重复插入某个值的时候，会覆盖之前的值，这个没错。但是对于多线程访问的时候，由于其内部实现机制(在多线程环境且未作同步的情况下，对同一个HashMap做put操作可能导致两个或以上线程同时做rehash动作，就可能导致循环键表出现，一旦出现线程将无法终止，持续占用CPU，导致CPU使用率居高不下)，就可能出现安全问题了。

HashMap效率

• 需求：测试下不同的初始化大小以及 key 值的 HashCode 值的分布情况的不同对 HashMap 效率的影响

• 测试初始化大小对 HashMap 的性能影响！！！

  • 首先来定义作为 Key 的类，hashCode() 方法直接返回其包含的属性 value。

    public class Key {
    
        private int value;
    
        public Key(int value) {
            this.value = value;
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Key key = (Key) o;
            return value == key.value;
        }
    
        @Override
        public int hashCode() {
            return value;
        }
    }
    
    private static final int MAX_KEY = 20000;
    private static final Key[] KEYS = new Key[MAX_KEY];
    
    private void testHashMap(){
        for (int i = 0; i < MAX_KEY; i++) {
            KEYS[i] = new Key(i);
        }
        //测试
        for (int i = 20; i <= MAX_KEY; i *= 10) {
            test(i);
        }
    }
    
    private static void test(int size) {
        long startTime = System.currentTimeMillis();
        Map<Key, Integer> map = new HashMap<>(size);
        for (int i = 0; i < MAX_KEY; i++) {
            map.put(KEYS[i], i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("yc---初始化大小是：" + size + " , 所用时间：" + (endTime - startTime) + "毫秒");
    }

  • 初始化大小从 100 到 100000 之间以 10 倍的倍数递增，向 HashMap 存入同等数据量的数据，观察不同 HashMap 存入数据消耗的总时间。例子中，各个Key对象之间的哈希码值各不相同，所以键值对在哈希桶数组中的分布可以说是很均匀的了，此时主要影响性能的就是扩容机制了,可以看出各个初始化大小对 HashMap 的性能影响还是很大的。

    yc---初始化大小是：20 , 所用时间：20毫秒
    yc---初始化大小是：200 , 所用时间：5毫秒
    yc---初始化大小是：2000 , 所用时间：0毫秒

• 然后测试Key对象之间频繁发生哈希冲突时HashMap的性能

  • 令 Key 类的 hashCode() 方法固定返回 100，则每个键值对在存入 HashMap 时，一定会发生哈希冲突。可以看到此时存入同等数据量的数据所用时间呈几何数增长了，此时主要影响性能的点就在于对哈希冲突的处理

    HashMap性能分析yc---初始化大小是：20 , 所用时间：281毫秒
    yc---初始化大小是：200 , 所用时间：246毫秒
    yc---初始化大小是：2000 , 所用时间：213毫秒

HashMap性能分析

• 查找key的时候，时间复杂度是 O(1)，同时它也花费了更多的内存空间。
  • 缺点:
  • 自动装箱的存在意味着每一次插入都会有额外的对象创建。这跟垃圾回收机制一样也会影响到内存的利用。
  • HashMap.Entry 对象本身是一层额外需要被创建以及被垃圾回收的对象。
  • “桶” 在 HashMap 每次被压缩或扩容的时候都会被重新安排。这个操作会随着对象数量的增长而变得开销极大。
• 对于查找一个key时，HashMap会发生什么 ?
  • 键的哈希值先被计算出来
  • 在 mHashes[] 数组中二分查找此哈希值。这表明查找的时间复杂度增加到了 O(logN)。
  • 一旦得到了哈希值所对应的索引 index，键值对中的键就存储在 mArray[2index] ，值存储在 mArray[2index+1]。
  • 这里的时间复杂度从 O(1) 上升到 O(logN)，但是内存效率提升了。当我们在 100 左右的数据量范围内尝试时，没有耗时的问题，察觉不到时间上的差异，但我们应用的内存效率获得了提高。
• Android中推荐使用ArrayMap或者SparseArray替代HashMap
  • 在Android中，当涉及到快速响应的应用时，内存至关重要，因为持续地分发和释放内存会出发垃圾回收机制，这会拖慢应用运行。
  • 垃圾回收时间段内，应用程序是不会运行的，最终应用使用上就显得卡顿。
  • ArrayMap 使用2个数组。它的对象实例内部有用来存储对象的 Object[] mArray 和 存储哈希值的 int[] mHashes。当插入一个键值对时：
    • 键/值被自动装箱。
    • 键对象被插入到 mArray[] 数组中的下一个空闲位置。
    • 值对象也会被插入到 mArray[] 数组中与键对象相邻的位置。
    • 键的哈希值会被计算出来并被插入到 mHashes[] 数组中的下一个空闲位置。

HashTable和HashMap

• HashTable和HashMap初始化与增长方式
  • 初始化时：
    • HashTable在不指定容量的情况下的默认容量为11，且不要求底层数组的容量一定要为2的整数次幂；
    • HashMap默认容量为16，且要求容量一定为2的整数次幂。
  • 扩容时：
    • Hashtable将容量变为原来的2倍加1；
    • HashMap扩容将容量变为原来的2倍。
• HashTable和HashMap线程安全性
  • HashTable其方法函数都是同步的（采用synchronized修饰），不会出现两个线程同时对数据进行操作的情况，因此保证了线程安全性。也正因为如此，在多线程运行环境下效率表现非常低下。因为当一个线程访问HashTable的同步方法时，其他线程也访问同步方法就会进入阻塞状态。比如当一个线程在添加数据时候，另外一个线程即使执行获取其他数据的操作也必须被阻塞，大大降低了程序的运行效率，在新版本中已被废弃，不推荐使用。
  • HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步（1）可以用Collections的synchronizedMap方法；（2）使用ConcurrentHashMap类，相较于HashTable锁住的是对象整体，ConcurrentHashMap基于lock实现锁分段技术。首先将Map存放的数据分成一段一段的存储方式，然后给每一段数据分配一把锁，当一个线程占用锁访问其中一个段的数据时，其他段的数据也能被其他线程访问。ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性，而且性能上有长足的提升。

LinkedHashMap

• 概述

  • 底层的数据结构是链表和哈希表，元素有序(具有可预知的迭代顺序)并且唯一。
  • 由哈希表保证键的唯一性
  • 由链表保证键盘的有序(存储和取出的顺序一致)

• 示例

  • LinkedHashMap的迭代输出的结果保持了插入顺序。

  LinkedHashMap<String, Integer> lmap = new LinkedHashMap<String, Integer>();
  lmap.put("语文", 1);
  lmap.put("数学", 2);
  lmap.put("英语", 3);
  lmap.put("历史", 4);
  lmap.put("政治", 5);
  lmap.put("地理", 6);
  lmap.put("生物", 7);
  lmap.put("化学", 8);
  for(Entry<String, Integer> entry : lmap.entrySet()) {
      System.out.println(entry.getKey() + ": " + entry.getValue());
  }
  // 运行结果是：
  
  语文: 1
  数学: 2
  英语: 3
  历史: 4
  政治: 5
  地理: 6
  生物: 7
  化学: 8

  

LinkedHashMap特点

• 官方文档所说：

  Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

• 具备特点

  • LinkedHashMap是Hash表和链表的实现，并且依靠着双向链表保证了迭代顺序是插入的顺序。

• 为何有LinkedHashMap

  • HashMap 是用于映射(键值对)处理的数据类型，不保证元素的顺序按照插入顺序来排列，为了解决这一问题，Java 在 JDK1.4 以后提供了 LinkedHashMap 来实现有序的 HashMap。

• LinkedHashMap 是 HashMap 的子类

  • 它保留了元素的插入顺序，在内部维护着一个按照元素插入顺序或者元素访问顺序来排列的链表，默认是按照元素的插入顺序来排列，就像使用 ArrayList 一样；
  • 如果是按照元素的访问顺序来排列，则访问元素后该元素将移至链表的尾部，可以以此来实现 LRUcache 缓存算法。

LinkedHashMap的Entry 节点类

• 前面说了，LinkedHashMap 是 HashMap 的子类

  • 即 LinkedHashMap 的主要数据结构实现还是依靠 HashMap 来实现，LinkedHashMap 只是对 HashMap 做的一层外部包装，这个从 LinkedHashMap 内声明的结点类就可以看出来。
  • Entry 类在 Node 类的基础上扩展了两个新的成员变量，这两个成员变量就是 LinkedHashMap 来实现有序访问的关键，不管结点对象在 HashMap 内部为了解决哈希冲突采用的是链表还是红黑树，这两个变量的指向都不受数据结构的变化而影响

• 从这也可以看出集合框架在设计时一个很巧妙的地方

  • LinkedHashMap 内部没有新建一个链表用来维护元素的插入顺序，而是通过扩展父类来实现自身的功能

  //LinkedHashMap 扩展了 HashMap.Node 类
  //在其基础上新增了两个成员变量用于指定上一个结点 before 和下一个结点 after
  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);
      }
  }

LinkedHashMap的实现函数

• 在HashMap中提到了下面的定义：

  // Callbacks to allow LinkedHashMap post-actions
  void afterNodeAccess(Node<K,V> p) { }
  void afterNodeInsertion(boolean evict) { }
  void afterNodeRemoval(Node<K,V> p) { }

• LinkedHashMap继承于HashMap，因此也重新实现了这3个函数，顾名思义这三个函数的作用分别是：节点访问后、节点插入后、节点移除后做一些事情。

• 从下面3个函数看出来，基本上都是为了保证双向链表中的节点次序或者双向链表容量所做的一些额外的事情，目的就是保持双向链表中节点的顺序要从eldest到youngest。

afterNodeAccess函数

• afterNodeAccess函数如下所示

  void afterNodeAccess(Node<K,V> e) { // move node to last
      LinkedHashMap.Entry<K,V> last;
      // 如果定义了accessOrder，那么就保证最近访问节点放到最后
      if (accessOrder && (last = tail) != e) {
          LinkedHashMap.Entry<K,V> p =
              (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
          p.after = null;
          if (b == null)
              head = a;
          else
              b.after = a;
          if (a != null)
              a.before = b;
          else
              last = b;
          if (last == null)
              head = p;
          else {
              p.before = last;
              last.after = p;
          }
          tail = p;
          ++modCount;
      }
  }

• 就是说在进行put之后就算是对节点的访问了，那么这个时候就会更新链表，把最近访问的放到最后，保证链表。

afterNodeInsertion函数

• 代码如下所示

  void afterNodeInsertion(boolean evict) { // possibly remove eldest
      LinkedHashMap.Entry<K,V> first;
      // 如果定义了溢出规则，则执行相应的溢出
      if (evict && (first = head) != null && removeEldestEntry(first)) {
          K key = first.key;
          removeNode(hash(key), key, null, false, true);
      }
  }

• 如果用户定义了removeEldestEntry的规则，那么便可以执行相应的移除操作。

afterNodeRemoval函数

• 代码如下所示

  void afterNodeRemoval(Node<K,V> e) { // unlink
      // 从链表中移除节点
      LinkedHashMap.Entry<K,V> p =
          (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
      p.before = p.after = null;
      if (b == null)
          head = a;
      else
          b.after = a;
      if (a == null)
          tail = b;
      else
          a.before = b;
  }

• 这个函数是在移除节点后调用的，就是将节点从双向链表中删除。

LinkedHashMap成员变量

• 变量 accessOrder 用于决定 LinkedHashMap 中元素的排序方式，变量 tail 则用于帮助当 accessOrder 为 true 时最新使用的一个结点的指向。

  //序列化ID
  private static final long serialVersionUID = 3801124242820219131L;
  
  //指向双向链表的头结点
  transient LinkedHashMap.Entry<K,V> head;
  
  //指向最新插入的一个结点
  transient LinkedHashMap.Entry<K,V> tail;
  
  //如果为true，则内部元素按照访问顺序排序
  //如果为false，则内部元素按照插入顺序排序
  final boolean accessOrder;

LinkedHashMap构造函数

• 构造函数如下所示，一般用无参构造方法。

  //自定义初始容量与装载因子
  //内部元素按照插入顺序进行排序
  public LinkedHashMap(int initialCapacity, float loadFactor) {
      super(initialCapacity, loadFactor);
      accessOrder = false;
  }
  
  //自定义装载因子
  //内部元素按照插入顺序进行排序
  public LinkedHashMap(int initialCapacity) {
      super(initialCapacity);
      accessOrder = false;
  }
  
  //使用默认的初始容量以及装载因子
  //内部元素按照插入顺序进行排序
  public LinkedHashMap() {
      super();
      accessOrder = false;
  }
  
  //使用初始数据
  //内部元素按照插入顺序进行排序
  public LinkedHashMap(Map<? extends K, ? extends V> m) {
      super();
      accessOrder = false;
      putMapEntries(m, false);
  }
  
  /**
   * @param  initialCapacity 初始容量
   * @param  loadFactor      装载因子
   * @param  accessOrder     如果为true，则内部元素按照访问顺序排序；如果为false，则内部元素按照插入顺序排序
   */
  public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
      super(initialCapacity, loadFactor);
      this.accessOrder = accessOrder;
  }

LinkedHashMap方法源码

put插入元素分析

• 在 HashMap 中有三个空实现的函数，源码注释中也写明这三个函数是准备由 LinkedHashMap 来实现的

  // Callbacks to allow LinkedHashMap post-actions
  void afterNodeAccess(Node<K,V> p) { }
  void afterNodeInsertion(boolean evict) { }
  void afterNodeRemoval(Node<K,V> p) { }

• 当中，如果在调用 put(K key, V value) 方法插入元素时覆盖了原有值，则afterNodeAccess 方法会被调用，该方法用于将最新访问的键值对移至链表的尾部，其在 LinkedHashMap 的实现如下所示

  //当访问了结点 e 时调用
  //结点 e 是最新访问的一个结点，此处将结点 e 置为链表的尾结点
  void afterNodeAccess(Node<K,V> e) {
      //last 用来指向链表的尾结点
      LinkedHashMap.Entry<K,V> last;
      //只有当上一次访问的结点不是结点 e 时（(last = tail) != e），才需要进行下一步操作
      if (accessOrder && (last = tail) != e) {
          //p 是最新访问的一个结点，b 是结点 p 的上一个结点，a 是结点 p 的下一个结点
          LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
          //因为结点 p 将成为尾结点，所以 after 置为null
          p.after = null;
          //如果 b == null ，说明结点 p 是原链表的头结点，则此时将 head 指向下一个结点 a
          //如果 b != null ，则移除结点 b 对结点 p 的引用
          if (b == null)
              head = a;
          else
              b.after = a;
          //如果 a !=null，说明结点 p 不是原链表的尾结点，则移除结点 a 对结点 p 的引用
          //如果 a == null，则说明结点 p 是原链表的尾结点，则让 last 指向结点 b
          if (a != null)
              a.before = b;
          else
              last = b;
          //如果 last == null，说明原链表为空，则此时头结点就是结点 p
          //如果 last != null，则建立 last 和实际尾结点 p 之间的引用
          if (last == null)
              head = p;
          else {
              p.before = last;
              last.after = p;
          }
          //最新一个引用到的结点就是 tail
          tail = p;
          ++modCount;
      }
  }

• 此外，当 put 方法调用结束时，afterNodeInsertion 方法会被调用，用于判断是否移除最近最少使用的元素，依此可以来构建 LRUcache 缓存

  //在插入元素后调用，此方法可用于 LRUcache 算法中移除最近最少使用的元素
  void afterNodeInsertion(boolean evict) {
      LinkedHashMap.Entry<K,V> first;
      if (evict && (first = head) != null && removeEldestEntry(first)) {
          K key = first.key;
          removeNode(hash(key), key, null, false, true);
      }
  }
  
  //如果在构造函数中参数 accessOrder 传入了 true ，则链表将按照访问顺序来排列
  //即最新访问的结点将处于链表的尾部，依此可以来构建 LRUcache 缓存
  //此方法就用于决定是否移除最旧的缓存，默认返回 false
  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
      return false;
  }

get访问元素

• 在访问元素时，如果 accessOrder 为 true ，则会将访问的元素移至链表的尾部，由于链表内结点位置的改变仅仅是修改几个引用即可，所以这个操作还是非常轻量级的 。

  //获取键值为 key 的键值对的 value
  public V get(Object key) {
      Node<K,V> e;
      if ((e = getNode(hash(key), key)) == null)
          return null;
      if (accessOrder)
          afterNodeAccess(e);
      return e.value;
  }
  
  //获取键值为 key 的键值对的 value，如果 key 不存在，则返回默认值 defaultValue
  public V getOrDefault(Object key, V defaultValue) {
     Node<K,V> e;
     if ((e = getNode(hash(key), key)) == null)
         return defaultValue;
     if (accessOrder)
         afterNodeAccess(e);
     return e.value;
  }

移除元素源码分析

• 当 HashMap 内部移除了某个结点时，LinkedHashMap 也要移除维护的链表中对该结点的引用，对应的是以下方法

  //在移除结点 e 后调用
  void afterNodeRemoval(Node<K,V> e) {
      //结点 b 指向结点 e 的上一个结点，结点 a 指向结点 e 的下一个结点
      LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
      //移除结点 p 对相邻结点的引用
      p.before = p.after = null;
      //如果 b == null，说明结点 p 是原链表的头结点，则移除结点 p 后新的头结点是 a
      //如果 b != null，则更新结点间的引用
      if (b == null)
          head = a;
      else
          b.after = a;
      //如果 a == null，说明结点 a 是尾结点，则移除结点 p 后最新一个访问的结点就是原倒数第二的结点
      //如果 a != null，则更新结点间的引用
      if (a == null)
          tail = b;
      else
          a.before = b;
  }

LRUCache拓展训练

• 在 Android 的实际应用开发中，LRUCache 算法是很常见的，一种典型的用途就是用来在内存中缓存 Bitmap，因为从 IO 流中读取 Bitmap 的代价很大，为了防止多次从磁盘中读取某张图片，所以可以选择在内存中缓存 Bitmap。但内存空间也是有限的，所以也不能每张图片都进行缓存，需要有选择性地缓存一定数量的图片，而最近最少使用算法（LRUCache）是一个可行的选择

• 这里利用 LinkedHashMap 可以按照元素使用顺序进行排列的特点，来实现一个 LRUCache 策略的缓存

  public class LRUCache {
  
      private static class LRUCacheMap<K, V> extends LinkedHashMap<K, V> {
  
          //最大的缓存数量
          private final int maxCacheSize;
  
          public LRUCacheMap(int maxCacheSize) {
              super(16, 0.75F, true);
              this.maxCacheSize = maxCacheSize;
          }
  
          @Override
          protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
              return size() > maxCacheSize;
          }
  
      }
  
      public static void main(String[] args) {
          //最大的缓存数量
          final int maxCacheSize = 5;
          LRUCacheMap<String, Integer> map = new LRUCacheMap<>(maxCacheSize);
          for (int i = 0; i < maxCacheSize; i++) {
              map.put("leavesC_" + i, i);
          }
          //输出结果是：leavesC_0 leavesC_1 leavesC_2 leavesC_3 leavesC_4
          System.out.println();
          Set<String> keySet = map.keySet();
          keySet.forEach(key -> System.out.print(key + " "));
  
          //获取链表的头结点的值，使之移动到链表尾部
          map.get("leavesC_0");
          System.out.println();
          keySet = map.keySet();
          //输出结果是：//leavesC_1 leavesC_2 leavesC_3 leavesC_4 leavesC_0
          keySet.forEach(key -> System.out.print(key + " "));
  
          //向链表添加元素，使用达到缓存的最大数量
          map.put("leavesC_5", 5);
          System.out.println();
          //输出结果是：//leavesC_2 leavesC_3 leavesC_4 leavesC_0 leavesC_5
          //最近最少使用的元素 leavesC_1 被移除了
          keySet.forEach(key -> System.out.print(key + " "));
      }
  }

TreeMap

• 结构特点

  • 键的数据结构是红黑树,可保证键的排序和唯一性
  • 排序分为自然排序和比较器排序，如果使用的是自然排序,对元素有要求,要求这个元素需要实现 Comparable 接口
  • 线程是不安全的效率比较高

• 排序通过构造器

  public TreeMap(): 自然排序
  public TreeMap(Comparator<? super K> comparator):  使用的是比较器排序

• 何时用TreeMap

  • HashMap不保证数据有序，LinkedHashMap保证数据可以保持插入顺序，而如果我们希望Map可以保持key的大小顺序的时候，我们就需要利用TreeMap了。

TreeMap的构造函数和类成员变量

• 构造函数

  // 默认构造函数。使用该构造函数，TreeMap中的元素按照自然排序进行排列。
  TreeMap()
  
  // 创建的TreeMap包含Map
  TreeMap(Map<? extends K, ? extends V> copyFrom)
  
  // 指定Tree的比较器
  TreeMap(Comparator<? super K> comparator)
  
  // 创建的TreeSet包含copyFrom
  TreeMap(SortedMap<K, ? extends V> copyFrom)

• 类成员变量

  • 我们可以看到 TreeMap 有一个 Entry 类型的 root 节点，而 Entry 则是 TreeMap 的内部类。
  • 从 TreeMap.Entry 的属性我们可以知道其实一个红黑树节点的实现。

  // 比较器。根据这个比较器决定TreeMap的排序。
  // 如果为空，表示按照key做自然排序（最小的在根节点）。
  private final Comparator<? super K> comparator;
  // 根节点
  private transient Entry<K,V> root;
  // 大小
  private transient int size = 0;
  // Node节点声明
  static final class Entry<K,V> implements Map.Entry<K,V> {
      K key;
      V value;
      Entry<K,V> left;
      Entry<K,V> right;
      Entry<K,V> parent;
      boolean color = BLACK;
  }

TreeMap简单使用

TreeMap<String,String>

• TreeMap集合键是String值是String的案例

// 创建集合对象
TreeMap<String, String> tm = new TreeMap<String, String>();

// 创建元素并添加元素
tm.put("hello", "你好");
tm.put("world", "世界");
tm.put("java", "爪哇");
tm.put("world", "世界2");
tm.put("javaee", "爪哇EE");

// 遍历集合
// 获取键
Set<String> set = tm.keySet();
for (String key : set) {
    // 获取值
    String value = tm.get(key);
    System.out.println(key + "---" + value);
}

结果:
hello---你好
java---爪哇
javaee---爪哇EE
world---世界2

TreeMap<Student,String>

• TreeMap集合键是Student值是String的案例,按照年龄大小进行排序,年龄相等根据名字排序

  // 创建集合对象
  TreeMap<Student, String> tm = new TreeMap<Student, String>(
  		new Comparator<Student>() {
  			@Override
  			public int compare(Student s1, Student s2) {
  				// 主要条件
  				int num = s1.getAge() - s2.getAge();
  				// 次要条件
  				int num2 = num == 0 ? s1.getName().compareTo(
  						s2.getName()) : num;
  				return num2;
  			}
  		});
  
  // 创建学生对象
  Student s1 = new Student("潘安", 30);
  Student s2 = new Student("柳下惠", 35);
  Student s3 = new Student("唐伯虎", 33);
  Student s4 = new Student("燕青", 32);
  Student s5 = new Student("唐伯虎", 33);
  
  // 存储元素
  tm.put(s1, "宋朝");
  tm.put(s2, "元朝");
  tm.put(s3, "明朝");
  tm.put(s4, "清朝");
  tm.put(s5, "汉朝");
  
  // 遍历
  Set<Student> set = tm.keySet();
  for (Student key : set) {
  	String value = tm.get(key);
  	System.out.println(key.getName() + "---" + key.getAge() + "---"
  			+ value);
  }
  结果:
  	潘安---30---宋朝
  	燕青---32---清朝
  	唐伯虎---33---汉朝
  	柳下惠---35---元朝

获取字符串字母出现的次数

• “aababcabcdabcde”，要求结果:a(5)b(4)c(3)d(2)e(1)

• 分析:

  1. 遍历字符串,获取每一个字符,然后将当前的字符作为键 , 上map集合中查找对应的值
  

  2. 如果返回的值不是null 对值进行+1 , 在把当前的元素作为键 , 值是+1以后的结果存储到集合中
  3. 如果返回的是是null , 不存在 , 就把当前遍历的元素作为键 , 1 作为值,添加到集合中

• 代码如下

  public static void main(String[] args) {
      // 定义字符串
      String s = "aababcabcdabcde" ;
      // 创建TreeMap集合对象
      TreeMap<Character , Integer> tm = new TreeMap<Character , Integer>() ;
      // 遍历字符串
      for(int x = 0 ; x < s.length() ; x++) {
          // 获取当前索引出对应的字符
          char ch = s.charAt(x) ;
          // 找值
          Integer value = tm.get(ch) ;
          // 判断
          if(value == null) {
              tm.put(ch, 1) ;
          }else {
              value += 1 ;
              tm.put(ch, value) ;
          }
      }
      // 遍历Map集合按照指定的形式拼接字符串
      StringBuilder sb = new StringBuilder() ;
      Set<Entry<Character,Integer>> entrySet = tm.entrySet() ;
      for(Entry<Character,Integer> en : entrySet) {
          // 获取键
          Character key = en.getKey() ;
          // 获取值
          Integer value = en.getValue() ;
          // a(5)b(4)c(3)d(2)e(1)
          // 拼接
          sb.append(key).append("(").append(value).append(")") ;
      }
      // 把sb转换成String
      String result = sb.toString() ;
      // 输出
      System.out.println(result);
  }

TreeMap方法源码

put函数源码

• 如果存在的话，old value被替换；如果不存在的话，则新添一个节点，然后对做红黑树的平衡操作。

  public V put(K key, V value) {
      Entry<K,V> t = root;
      if (t == null) {
          compare(key, key); // type (and possibly null) check
          root = new Entry<>(key, value, null);
          size = 1;
          modCount++;
          return null;
      }
      int cmp;
      Entry<K,V> parent;
      // split comparator and comparable paths
      Comparator<? super K> cpr = comparator;
          // 如果该节点存在，则替换值直接返回
      if (cpr != null) {
          do {
              parent = t;
              cmp = cpr.compare(key, t.key);
              if (cmp < 0)
                  t = t.left;
              else if (cmp > 0)
                  t = t.right;
              else
                  return t.setValue(value);
          } while (t != null);
      }
      else {
          if (key == null)
              throw new NullPointerException();
          @SuppressWarnings("unchecked")
              Comparable<? super K> k = (Comparable<? super K>) key;
          do {
              parent = t;
              cmp = k.compareTo(t.key);
              if (cmp < 0)
                  t = t.left;
              else if (cmp > 0)
                  t = t.right;
              else
                  return t.setValue(value);
          } while (t != null);
      }
      // 如果该节点未存在，则新建
      Entry<K,V> e = new Entry<>(key, value, parent);
      if (cmp < 0)
          parent.left = e;
      else
          parent.right = e;
  
      // 红黑树平衡调整
      fixAfterInsertion(e);
      size++;
      modCount++;
      return null;
  }

get获取函数源码

• get函数则相对来说比较简单，以log(n)的复杂度进行get。

  final Entry<K,V> getEntry(Object key) {
      // Offload comparator-based version for sake of performance
      if (comparator != null)
          return getEntryUsingComparator(key);
      if (key == null)
          throw new NullPointerException();
      @SuppressWarnings("unchecked")
          Comparable<? super K> k = (Comparable<? super K>) key;
      Entry<K,V> p = root;
          // 按照二叉树搜索的方式进行搜索，搜到返回
      while (p != null) {
          int cmp = k.compareTo(p.key);
          if (cmp < 0)
              p = p.left;
          else if (cmp > 0)
              p = p.right;
          else
              return p;
      }
      return null;
  }
  public V get(Object key) {
      Entry<K,V> p = getEntry(key);
      return (p==null ? null : p.value);
  }

remove删除

• TreeMap 的删除其实就是红黑树的删除

  public V remove(Object key) {
      Entry<K,V> p = getEntry(key);
      if (p == null)
          return null;
  
      V oldValue = p.value;
      deleteEntry(p);
      return oldValue;
  }
  
  private void deleteEntry(Entry<K,V> p) {
      modCount++;
      size--;
  
      /*
       * 1. 如果 p 有两个孩子节点，则找到后继节点，
       * 并把后继节点的值复制到节点 P 中，并让 p 指向其后继节点
       */
      if (p.left != null && p.right != null) {
          Entry<K,V> s = successor(p);
          p.key = s.key;
          p.value = s.value;
          p = s;
      } // p has 2 children
  
      // Start fixup at replacement node, if it exists.
      Entry<K,V> replacement = (p.left != null ? p.left : p.right);
  
      if (replacement != null) {
          /*
           * 2. 将 replacement parent 引用指向新的父节点，
           * 同时让新的父节点指向 replacement。
           */
          replacement.parent = p.parent;
          if (p.parent == null)
              root = replacement;
          else if (p == p.parent.left)
              p.parent.left  = replacement;
          else
              p.parent.right = replacement;
  
          // Null out links so they are OK to use by fixAfterDeletion.
          p.left = p.right = p.parent = null;
  
          // 3. 如果删除的节点 p 是黑色节点，则需要进行调整
          if (p.color == BLACK)
              fixAfterDeletion(replacement);
      } else if (p.parent == null) { // 删除的是根节点，且树中当前只有一个节点
          root = null;
      } else { // 删除的节点没有孩子节点
          // p 是黑色，则需要进行调整
          if (p.color == BLACK)
              fixAfterDeletion(p);
  
          // 将 P 从树中移除
          if (p.parent != null) {
              if (p == p.parent.left)
                  p.parent.left = null;
              else if (p == p.parent.right)
                  p.parent.right = null;
              p.parent = null;
          }
      }
  }

keySet 遍历

• TreeMap 会从小到大输出键的值。那么，接下来就来分析一下keySet方法，以及在遍历 keySet 方法产生的集合时，TreeMap 是如何保证键的有序性的。

  • 核心代码还是 KeySet 类和 PrivateEntryIterator 类的 nextEntry方法。
  • 在初始化 KeyIterator 时，默认情况下会将 TreeMap 中包含最小键或最大值（取决于传入的比较器）的 Entry 传给 PrivateEntryIterator。
  • 当调用 nextEntry 方法时，通过调用 successor 方法找到当前 entry 的后继，并让 next 指向后继，最后返回当前的 entry。通过这种方式即可实现按正序返回键值的的逻辑。

  public Set<K> keySet() {
      return navigableKeySet();
  }
  
  public NavigableSet<K> navigableKeySet() {
      KeySet<K> nks = navigableKeySet;
      return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
  }
  
  static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
      private final NavigableMap<E, ?> m;
      KeySet(NavigableMap<E,?> map) { m = map; }
  
      public Iterator<E> iterator() {
          if (m instanceof TreeMap)
              return ((TreeMap<E,?>)m).keyIterator();
          else
              return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
      }
  
      // 省略非关键代码
  }
  
  Iterator<K> keyIterator() {
      return new KeyIterator(getFirstEntry());
  }
  
  final class KeyIterator extends PrivateEntryIterator<K> {
      KeyIterator(Entry<K,V> first) {
          super(first);
      }
      public K next() {
          return nextEntry().key;
      }
  }
  
  abstract class PrivateEntryIterator<T> implements Iterator<T> {
      Entry<K,V> next;
      Entry<K,V> lastReturned;
      int expectedModCount;
  
      PrivateEntryIterator(Entry<K,V> first) {
          expectedModCount = modCount;
          lastReturned = null;
          next = first;
      }
  
      public final boolean hasNext() {
          return next != null;
      }
  
      final Entry<K,V> nextEntry() {
          Entry<K,V> e = next;
          if (e == null)
              throw new NoSuchElementException();
          if (modCount != expectedModCount)
              throw new ConcurrentModificationException();
          // 寻找节点 e 的后继节点
          next = successor(e);
          lastReturned = e;
          return e;
      }
  
      // 其他方法省略
  }

TreeMap如何保证有序性

• TreeMap是如何保证其迭代输出是有序的呢？

  • 其实从宏观上来讲，就相当于树的中序遍历(LDR)。我们先看一下迭代输出的步骤

  for(Entry<Integer, String> entry : tmap.entrySet()) {
      System.out.println(entry.getKey() + ": " + entry.getValue());
  }

• for语句会做如下转换为：

  for(Iterator<Map.Entry<String, String>> it = tmap.entrySet().iterator() ; tmap.hasNext(); ) {
      Entry<Integer, String> entry = it.next();
      System.out.println(entry.getKey() + ": " + entry.getValue());
  }

• 在it.next()的调用中会使用nextEntry调用successor这个是过的后继的重点。

• 然后看一下successor函数

  static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
      if (t == null)
          return null;
      else if (t.right != null) {
          // 有右子树的节点，后继节点就是右子树的“最左节点”
          // 因为“最左子树”是右子树的最小节点
          Entry<K,V> p = t.right;
          while (p.left != null)
              p = p.left;
          return p;
      } else {
          // 如果右子树为空，则寻找当前节点所在左子树的第一个祖先节点
          // 因为左子树找完了，根据LDR该D了
          Entry<K,V> p = t.parent;
          Entry<K,V> ch = t;
          // 保证左子树
          while (p != null && ch == p.right) {
              ch = p;
              p = p.parent;
          }
          return p;
      }
  }

• 怎么理解这个successor呢？只要记住，这个是中序遍历就好了，L-D-R。具体细节如下：

  • a. 空节点，没有后继
  • b. 有右子树的节点，后继就是右子树的“最左节点”
  • c. 无右子树的节点，后继就是该节点所在左子树的第一个祖先节点

• 理解

  • 有右子树的节点，节点的下一个节点，肯定在右子树中，而右子树中“最左”的那个节点则是右树中最小的一个，那么当然是右子树的“最左节点”，就好像下图所示：
  • 
  • 无右子树的节点，先找到这个节点所在的左子树(右图)，那么这个节点所在的左子树的父节点(绿色节点)，就是下一个节点。
  • 

ConcurrentHashMap

HashMap使用的弊端

• HashMap是我们平时开发过程中用的比较多的集合，但它是非线程安全的，在涉及到多线程并发的情况，进行put操作有可能会引起死循环，导致CPU利用率接近100%。

  final HashMap<String, String> map = new HashMap<String, String>(2);
  for (int i = 0; i < 10000; i++) {
      new Thread(new Runnable() {
          @Override
          public void run() {
              map.put(UUID.randomUUID().toString(), "");
          }
      }).start();
  }

• 解决方案有Hashtable和Collections.synchronizedMap(hashMap)，不过这两个方案基本上是对读写进行加锁操作，一个线程在读写元素，其余线程必须等待，性能可想而知。

ConcurrentHashMap底层知识点

• 并发安全的ConcurrentHashMap，它的实现是依赖于 Java 内存模型，所以我们在了解 ConcurrentHashMap 的之前必须了解一些底层的知识：

• 1.java内存模型

• 2.java中的CAS

• 3.AbstractQueuedSynchronizer

• 4.ReentrantLock

ConcurrentHashMap JDK 1.6和JDK1.8区分

JDK1.6分析

• ConcurrentHashMap采用 分段锁的机制，实现并发的更新操作，底层采用数组+链表+红黑树的存储结构。

• 其包含两个核心静态内部类 Segment和HashEntry。

  • 1.Segment继承ReentrantLock用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶。
  • 2.HashEntry 用来封装映射表的键 / 值对；
  • 3.每个桶是由若干个 HashEntry 对象链接起来的链表。

• 一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组，下面我们通过一个图来演示一下 ConcurrentHashMap 的结构：

  ​

JDK1.8分析

• 1.8的实现已经抛弃了Segment分段锁机制，利用CAS+Synchronized来保证并发更新的安全，底层依然采用数组+链表+红黑树的存储结构。

• 概念介绍

  • table：默认为null，初始化发生在第一次插入操作，默认大小为16的数组，用来存储Node节点数据，扩容时大小总是2的幂次方。

  • nextTable：默认为null，扩容时新生成的数组，其大小为原数组的两倍。

  • sizeCtl

    • 默认为0，用来控制table的初始化和扩容操作，具体应用在后续会体现出来。
    • **-1 **代表table正在初始化
    • **-N **表示有N-1个线程正在进行扩容操作
    • 其余情况：
      • 如果table未初始化，表示table需要初始化的大小。
      • 如果table初始化完成，表示table的容量，默认是table大小的0.75倍，居然用这个公式算0.75（n - (n >>> 2)）。

  • Node

    • 保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。

    class Node<K,V> implements Map.Entry<K,V> {
     final int hash;
     final K key;
     volatile V val;
     volatile Node<K,V> next;
     ... 省略部分代码
    }

  • ForwardingNode

    • 一个特殊的Node节点，hash值为-1，其中存储nextTable的引用。只有table发生扩容的时候，ForwardingNode才会发挥作用，作为一个占位符放在table中表示当前节点为null或则已经被移动。

    final class ForwardingNode<K,V> extends Node<K,V> {
      final Node<K,V>[] nextTable;
      ForwardingNode(Node<K,V>[] tab) {
          super(MOVED, null, null, null);
          this.nextTable = tab;
      }
    }

ConcurrentHashMap原理

实例初始化 构造函数

• 实例化ConcurrentHashMap时带参数时，会根据参数调整table的大小，假设参数为100，最终会调整成256，确保table的大小总是2的幂次方，算法如下：

  ConcurrentHashMap<String, String> hashMap = new ConcurrentHashMap<>(100);
  private static final int tableSizeFor(int c) {
      int n = c - 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;
  }

• 注意

  • ConcurrentHashMap在构造函数中只会初始化sizeCtl值，并不会直接初始化table，而是延缓到第一次put操作。

table初始化 initTable()

• 前面已经提到过，table初始化操作会延缓到第一次put行为。

• 但是put是可以并发执行的，Doug Lea是如何实现table只初始化一次的？让我们来看看源码的实现。

  private final Node<K,V>[] initTable() {
      Node<K,V>[] tab; int sc;
      while ((tab = table) == null || tab.length == 0) {
          //如果一个线程发现sizeCtl<0，意味着另外的线程执行CAS操作成功，当前线程只需要让出cpu时间片
          if ((sc = sizeCtl) < 0)
              Thread.yield(); // lost initialization race; just spin
          else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
              try {
                  if ((tab = table) == null || tab.length == 0) {
                      int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                      @SuppressWarnings("unchecked")
                      Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                      table = tab = nt;
                      sc = n - (n >>> 2);
                  }
              } finally {
                  sizeCtl = sc;
              }
              break;
          }
      }
      return tab;
  }

• sizeCtl默认为0，如果ConcurrentHashMap实例化时有传参数，sizeCtl会是一个2的幂次方的值。

  • 所以执行第一次put操作的线程会执行Unsafe.compareAndSwapInt方法修改sizeCtl为-1，有且只有一个线程能够修改成功，其它线程通过Thread.yield()让出CPU时间片等待table初始化完成。

put插入数据操作

• 假设table已经初始化完成，put操作采用CAS+synchronized实现并发插入或更新操作，具体实现如下。

  final V putVal(K key, V value, boolean onlyIfAbsent) {
      if (key == null || value == null) throw new NullPointerException();
      int hash = spread(key.hashCode());
      int binCount = 0;
      for (Node<K,V>[] tab = table;;) {
          Node<K,V> f; int n, i, fh;
          if (tab == null || (n = tab.length) == 0)
              tab = initTable();
          else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
              if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                  break;                   // no lock when adding to empty bin
          }
          else if ((fh = f.hash) == MOVED)
              tab = helpTransfer(tab, f);
          ...省略部分代码
      }
      addCount(1L, binCount);
      return null;
  }

• 1.hash算法

  static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS;}

• 2.table中定位索引位置，n是table的大小

  int index = (n - 1) & hash

• 3.获取table中对应索引的元素f。

  • Doug Lea采用Unsafe.getObjectVolatile来获取，也许有人质疑，直接table[index]不可以么，为什么要这么复杂？
  • 在java内存模型中，我们已经知道每个线程都有一个工作内存，里面存储着table的副本，虽然table是volatile修饰的，但不能保证线程每次都拿到table中的最新元素，Unsafe.getObjectVolatile可以直接获取指定内存的数据，保证了每次拿到数据都是最新的。

• 4.如果f为null，说明table中这个位置第一次插入元素，利用Unsafe.compareAndSwapObject方法插入Node节点。

  • 如果CAS成功，说明Node节点已经插入，随后addCount(1L, binCount)方法会检查当前容量是否需要进行扩容。
  • 如果CAS失败，说明有其它线程提前插入了节点，自旋重新尝试在这个位置插入节点。

• 5.如果f的hash值为-1，说明当前f是ForwardingNode节点，意味有其它线程正在扩容，则一起进行扩容操作。

• 6.其余情况把新的Node节点按链表或红黑树的方式插入到合适的位置，这个过程采用同步内置锁实现并发，代码如下:

  synchronized (f) {
   if (tabAt(tab, i) == f) {
       if (fh >= 0) {
           binCount = 1;
           for (Node<K,V> e = f;; ++binCount) {
               K ek;
               if (e.hash == hash &&
                   ((ek = e.key) == key ||
                    (ek != null && key.equals(ek)))) {
                   oldVal = e.val;
                   if (!onlyIfAbsent)
                       e.val = value;
                   break;
               }
               Node<K,V> pred = e;
               if ((e = e.next) == null) {
                   pred.next = new Node<K,V>(hash, key,
                                             value, null);
                   break;
               }
           }
       }
       else if (f instanceof TreeBin) {
           Node<K,V> p;
           binCount = 2;
           if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                          value)) != null) {
               oldVal = p.val;
               if (!onlyIfAbsent)
                   p.val = value;
           }
       }
   }
  }

  • 在节点f上进行同步，节点插入之前，再次利用tabAt(tab, i) == f判断，防止被其它线程修改。
    • 1. 如果f.hash >= 0，说明f是链表结构的头结点，遍历链表，如果找到对应的node节点，则修改value，否则在链表尾部加入节点。
    • 2. 如果f是TreeBin类型节点，说明f是红黑树根节点，则在树结构上遍历元素，更新或增加节点。
    • 3. 如果链表中节点数binCount >= TREEIFY_THRESHOLD(默认是8)，则把链表转化为红黑树结构。

table扩容

• 当table容量不足的时候，即table的元素数量达到容量阈值sizeCtl，需要对table进行扩容。

• 整个扩容分为两部分：

  1. 构建一个nextTable，大小为table的两倍。
  2. 把table的数据复制到nextTable中。

• 这两个过程在单线程下实现很简单，但是ConcurrentHashMap是支持并发插入的，扩容操作自然也会有并发的出现，这种情况下，第二步可以支持节点的并发复制，这样性能自然提升不少，但实现的复杂度也上升了一个台阶。

• 先看第一步，构建nextTable，毫无疑问，这个过程只能只有单个线程进行nextTable的初始化，具体实现如下：

  • 通过Unsafe.compareAndSwapInt修改sizeCtl值，保证只有一个线程能够初始化nextTable，扩容后的数组长度为原来的两倍，但是容量是原来的1.5。

  private final void addCount(long x, int check) {
      ... 省略部分代码
      if (check >= 0) {
          Node<K,V>[] tab, nt; int n, sc;
          while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                 (n = tab.length) < MAXIMUM_CAPACITY) {
              int rs = resizeStamp(n);
              if (sc < 0) {
                  if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                      sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                      transferIndex <= 0)
                      break;
                  if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                      transfer(tab, nt);
              }
              else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                           (rs << RESIZE_STAMP_SHIFT) + 2))
                  transfer(tab, null);
              s = sumCount();
          }
      }
  }

• 节点从table移动到nextTable，大体思想是遍历、复制的过程。

  1. 首先根据运算得到需要遍历的次数i，然后利用tabAt方法获得i位置的元素f，初始化一个forwardNode实例fwd。
  2. 如果f == null，则在table中的i位置放入fwd，这个过程是采用Unsafe.compareAndSwapObjectf方法实现的，很巧妙的实现了节点的并发移动。
  3. 如果f是链表的头节点，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置上，移动完成，采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。
  4. 如果f是TreeBin节点，也做一个反序处理，并判断是否需要untreeify，把处理的结果分别放在nextTable的i和i+n的位置上，移动完成，同样采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。

• 遍历过所有的节点以后就完成了复制工作，把table指向nextTable，并更新sizeCtl为新数组大小的0.75倍 ，扩容完成。

红黑树构造

注意：如果链表结构中元素超过TREEIFY_THRESHOLD阈值，默认为8个，则把链表转化为红黑树，提高遍历查询效率。

if (binCount != 0) {
    if (binCount >= TREEIFY_THRESHOLD)
        treeifyBin(tab, i);
    if (oldVal != null)
        return oldVal;
    break;
}

• 接下来我们看看如何构造树结构，代码如下：

private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if (tab != null) {
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            synchronized (b) {
                if (tabAt(tab, index) == b) {
                    TreeNode<K,V> hd = null, tl = null;
                    for (Node<K,V> e = b; e != null; e = e.next) {
                        TreeNode<K,V> p =
                            new TreeNode<K,V>(e.hash, e.key, e.val,
                                              null, null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}

可以看出，生成树节点的代码块是同步的，进入同步代码块之后，再次验证table中index位置元素是否被修改过。
1、根据table中index位置Node链表，重新生成一个hd为头结点的TreeNode链表。
2、根据hd头结点，生成TreeBin树结构，并把树结构的root节点写到table的index位置的内存中，具体实现如下：

TreeBin(TreeNode<K,V> b) {
    super(TREEBIN, null, null, null);
    this.first = b;
    TreeNode<K,V> r = null;
    for (TreeNode<K,V> x = b, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (r == null) {
            x.parent = null;
            x.red = false;
            r = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = r;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                    TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    r = balanceInsertion(r, x);
                    break;
                }
            }
        }
    }
    this.root = r;
    assert checkInvariants(root);
}

主要根据Node节点的hash值大小构建二叉树。这个红黑树的构造过程实在有点复杂，感兴趣的同学可以看看源码。

get操作

get操作和put操作相比，显得简单了许多。

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

1. 判断table是否为空，如果为空，直接返回null。
2. 计算key的hash值，并获取指定table中指定位置的Node节点，通过遍历链表或则树结构找到对应的节点，返回value值。

总结

ConcurrentHashMap 是一个并发散列映射表的实现，它允许完全并发的读取，并且支持给定数量的并发更新。相比于 HashTable 和同步包装器包装的 HashMap，使用一个全局的锁来同步不同线程间的并发访问，同一时间点，只能有一个线程持有锁，也就是说在同一时间点，只能有一个线程能访问容器，这虽然保证多线程间的安全并发访问，但同时也导致对容器的访问变成串行化的了。

集合嵌套

HashMap嵌套HashMap

• 代码

  public static void main(String[] args) {
      // 创建大的集合对象
      HashMap<String , HashMap<String , Integer>> czbkMap = new HashMap<String , HashMap<String , Integer>>() ;
      // 创建基础班的HashMap集合
      HashMap<String , Integer> jcHashMap = new HashMap<String , Integer>() ;
      // 添加元素
      jcHashMap.put("陈玉楼", 20) ;
      jcHashMap.put("高跃", 22) ;
      // 把jcHashMap存储到czbkMap
      czbkMap.put("jc", jcHashMap) ;
      // 创建就业班的HashMap集合
      HashMap<String , Integer> jyHashMap = new HashMap<String , Integer>() ;
      // 添加元素
      jyHashMap.put("李杰", 21) ;
      jyHashMap.put("曹石磊", 23) ;
      // 把jcHashMap存储到czbkMap
      czbkMap.put("jy", jyHashMap) ;
      System.out.println("-------------------------------------------------------------------------------");
      // HashMap<String , HashMap<String , Integer>> czbkMap = new HashMap<String , HashMap<String , Integer>>() ;
      Set<Entry<String,HashMap<String,Integer>>> entrySet = czbkMap.entrySet() ;
      for(Entry<String,HashMap<String,Integer>> en : entrySet) {
          // 获取键
          String key = en.getKey() ;
          System.out.println(key);
          // 获取值
          HashMap<String,Integer> hashMap = en.getValue() ;
          // 遍历hashMap
          Set<String> keySet = hashMap.keySet() ;
          for(String hashMapkey : keySet){
              // 根据键找值
              Integer value = hashMap.get(hashMapkey) ;
              // 输出
              System.out.println("\t" + hashMapkey + "\t" + value);
          }
          // 换行
          System.out.println();
      }
  }

HashMap嵌套ArrayList

• 代码

  public static void main(String[] args) {
      // 创建大的集合对象
      HashMap<String , ArrayList<String>> xiaoShuoMap = new HashMap<String , ArrayList<String>>() ;
      // 创建三国演义的List集合
      ArrayList<String> sgList = new ArrayList<String>() ;
      // 添加元素
      sgList.add("吕布") ;
      sgList.add("周瑜") ;
      // 把sgList添加到xiaoShuoMap中
      xiaoShuoMap.put("三国演义", sgList) ;
      // 创建笑傲江湖的List集合
      ArrayList<String> xaList = new ArrayList<String>() ;
      // 添加元素
      xaList.add("林平之") ;
      xaList.add("令狐冲") ;
      // 把sgList添加到xiaoShuoMap中
      xiaoShuoMap.put("笑傲江湖", xaList) ;
      // 创建神雕侠侣的List集合
      ArrayList<String> sdList = new ArrayList<String>() ;
      // 添加元素
      sdList.add("杨过") ;
      sdList.add("郭靖") ;
      // 把sgList添加到xiaoShuoMap中
      xiaoShuoMap.put("神雕侠侣", sdList) ;
      // HashMap<String , ArrayList<String>> xiaoShuoMap = new HashMap<String , ArrayList<String>>() ;
      Set<Entry<String,ArrayList<String>>> entrySet = xiaoShuoMap.entrySet() ;
      for(Entry<String,ArrayList<String>> en : entrySet) {
          // 获取键
          String key = en.getKey() ;
          System.out.println(key);
          // 获取值
          ArrayList<String> value = en.getValue() ;
          // 遍历
          for(String name : value) {
              System.out.println("\t" + name);
          }
          System.out.println();
      }
  }

ArrayList嵌套HashMap

• 代码

  public static void main(String[] args) {
      // 创建大的集合对象
      ArrayList<HashMap<String , String>> al = new ArrayList<HashMap<String , String>>() ;
      // 创建小的HashMap集合
      HashMap<String , String> sgHashMap = new HashMap<String , String>() ;
      HashMap<String , String> xaHashMap = new HashMap<String , String>() ;
      HashMap<String , String> sdHashMap = new HashMap<String , String>() ;
      // 添加元素
      sgHashMap.put("吕布", "貂蝉") ;
      sgHashMap.put("周瑜", "小乔") ;
      xaHashMap.put("林平之", "岳灵珊") ;
      xaHashMap.put("令狐冲", "任盈盈") ;
      sdHashMap.put("郭靖", "黄蓉") ;
      sdHashMap.put("杨过", "小龙女") ;
      // 把小的HashMap添加到al中
      al.add(sgHashMap) ;
      al.add(xaHashMap) ;
      al.add(sdHashMap) ;
      // 遍历
      // ArrayList<HashMap<String , String>> al = new ArrayList<HashMap<String , String>>() ;
      for(HashMap<String , String> hm : al) {
          // 根据键值对对象进行遍历
          Set<Entry<String,String>> entrySet = hm.entrySet() ;
          for(Entry<String,String>  en : entrySet) {
              // 获取键
              String key = en.getKey() ;
              // 获取值
              String value = en.getValue() ;
              // 输出
              System.out.println(key + "---" + value);
          }
          System.out.println();
      }
  }