[数据结构与算法]hsahmap与红黑树(深层解析)

我们先来了解一下map集合

什么是Map集合？

Map用于保存具有映射关系的数据，Map集合里保存着两组值，一组用于保存Map的ley，另一组保存着Map的value。

?map集合的作用

?????? 和查字典类似，通过key找到对应的value，通过页数找到对应的信息。用学生类来说，key相当于学号，value对应name，age，sex等信息。用这种对应关系方便查找。

Map和Set的关系

?????? 可以说关系是很密切了，虽然Map中存放的时键值对，Set中存放的是单个对象，但如果把value看做key的附庸，key在哪里，value就在哪里，这样就可以像对待Set一样来对待Map了。事实上，Map提供了一个Entry内部类来封装key-value对，再计算Entry存储时则只考虑Entry封装的key。

?????? 如果把Map集合里的所有value放在一起来看，它们又类似于一个List，元素可以重复，每个元素可以根据索引来找，只是Map中的索引不再是整数值，而是以另一个对象作为索引。

看顶层共性方法找子类特有对象

Map与Collection在集合框架中属并列存在

Map存储的是键值对

Map存储元素使用put方法，Collection使用add方法

Map集合没有直接取出元素的方法，而是先转成Set集合，在通过迭代获取元素

Map集合中键要保证唯一性

Collection是单列集合, Map 是双列集合。

Map集合的三种迭代方式

使用keySet

将Map转成Set集合（keySet()），通过Set的迭代器取出Set集合中的每一个元素（Iterator）就是Map集合中的所有的键，再通过get方法获取键对应的值。

public class Demo2 {
	public static void main(String[] args) {
		Map<Integer, String> map = new HashMap<Integer, String>();
		map.put(1, "aaaa");
		map.put(2, "bbbb");
		map.put(3, "cccc");
		System.out.println(map);
 
		//
		// 获取方法：
		// 第一种方式: 使用keySet
		// 需要分别获取key和value，没有面向对象的思想
		// Set<K> keySet() 返回所有的key对象的Set集合
 
		Set<Integer> ks = map.keySet();
		Iterator<Integer> it = ks.iterator();
		while (it.hasNext()) {
			Integer key = it.next();
			String value = map.get(key);
			System.out.println("key=" + key + " value=" + value);
		}
	}
}

?通过values 获取所有值,不能获取到key对象

public static void main(String[] args) {
		Map<Integer, String> map = new HashMap<Integer, String>();
		map.put(1, "aaaa");
		map.put(2, "bbbb");
		map.put(3, "cccc");
		System.out.println(map);
// 第二种方式：
		// 通过values 获取所有值,不能获取到key对象
		// Collection<V> values()
 
		Collection<String> vs = map.values();
		Iterator<String> it = vs.iterator();
		while (it.hasNext()) {
			String value = it.next();
			System.out.println(" value=" + value);
		}
}

?第三种方式: Map.Entry

通过Map中的entrySet()方法获取存放Map.Entry<K,V>对象的Set集合。

Set<Map.Entry<K,V>> entrySet()

面向对象的思想将map集合中的键和值映射关系打包为一个对象，就是Map.Entry，将该对象存入Set集合，Map.Entry是一个对象，那么该对象具备的getKey，getValue获得键和值。

public static void main(String[] args) {
		Map<Integer, String> map = new HashMap<Integer, String>();
		map.put(1, "aaaa");
		map.put(2, "bbbb");
		map.put(3, "cccc");
		System.out.println(map);
		// 第三种方式： Map.Entry对象 推荐使用 重点
		// Set<Map.Entry<K,V>> entrySet()
		
 
		// 返回的Map.Entry对象的Set集合 Map.Entry包含了key和value对象
		Set<Map.Entry<Integer, String>> es = map.entrySet();
 
		Iterator<Map.Entry<Integer, String>> it = es.iterator();
 
		while (it.hasNext()) {
			
			// 返回的是封装了key和value对象的Map.Entry对象
			Map.Entry<Integer, String> en = it.next();
 
			// 获取Map.Entry对象中封装的key和value对象
			Integer key = en.getKey();
			String value = en.getValue();
 
			System.out.println("key=" + key + " value=" + value);
		}
	}

特点

• Map可以根据键来提取对应的值
• Map的键不允许重复,如果重复,对应的值会被覆盖
• Map存放的都是无序的数据
• Map的初始容量是16,默认的加载因子是0.75

hashmap

集合简介

HashMap是Java程序员使用最频繁的的用于键值对(key value)数据处理的容器，在JDK1.7(Java Developmet Kit）时HashMap采取的是数组+链表的形式存储数据，JDK1.8对HashMap进行了存储结构上的优化，引入了红黑树数据结构，极大的增强了HashMap的存取性能！

为什么会引入红黑树呢？

因为HashMap存在一个问题，即使负载因子和Hash算法设计的再合理，也无法避免出现在链表上拉链过长的问题，如果极端情况下出现严重的Hash冲突，会严重影响HashMap的存取性能，于是HashMap在jdk1.8时，引入红黑树，利用红黑树快速增删改查的特点来优化了HashMap的性能！

摘要:当创建hashmap的集合对象时,在jdk8以前,构造方法中创建一个长度是16的Entry[]table,来存储键值对的数据,而在jdk8以后,将不再那样做,而是在第一次调用put()方法是创建的数组Node()table来存储键值对的数据。

HashMap中的负载因子和容量

在介绍HashMap之前让我们先了解一下HashMap中的负载因子和容量这两个属性。

其实HashMap的实际容量如下：

实际容量 = 负载因子 x 容量，也就是 12 = 0.75 x 16

/默认初始容量-必须为2的幂次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量，如果传入的值大于下面的值，则使用下面定义的值
static final int MAXIMUM_CAPACITY = 1 << 30;

//在构造函数中未指定时使用的负载系数（上面提到的负载因子在这里出现了）
//默认加载因子为0.75（当表容量达到3/4时才会再散列）
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//当链表的长度 >= 8的时候，将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;

//在resize()扩容的时候，HashMap的数据存储位置会重新进行计算
//在重新就散存储的位置后，当原有的红黑树数量 <= 6 的时候，则将红黑树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;

//为了避免扩容/调整树化阀值之间的冲突，这个值不能 < 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

?