Java集合详解--Map_java map

1.Map概述

前面我们学习的Collection叫做集合，它可以快速查找现有的元素。
而Map在《Core Java》中称之为–>映射

HashMap：键值对，key不能重复，但是value可以重复；key的实现就是HashSet；value对应着放；允许null的键或值；
Hashtable：线程安全的，不允许null的键或值； Properties:：key和value都是String类型，用来读配置文件；
TreeMap：对key排好序的Map; key 就是TreeSet, value对应每个key;key要实现Comparable接口或TreeMap有自己的构造器；
LinkedHashMap：此实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。存储的数据是有序的。

1.1Map与Collection的区别

1.2Map常用功能

2.散列表介绍

无论是Set还是Map，我们会发现都会有对应的–>HashSet,HashMap
首先我们也先得回顾一下数组和链表：
• 链表和数组都可以按照人们的意愿来排列元素的次序，他们可以说是有序的(存储的顺序和取出的顺序是一致的)
• 但同时，这会带来缺点：想要获取某个元素，就要访问所有的元素，直到找到为止。
• 这会让我们消耗很多的时间在里边，遍历访问元素~
而还有另外的一些存储结构：不在意元素的顺序，能够快速的查找元素的数据
• 其中就有一种非常常见的：散列表

2.1散列表工作原理

散列表为每个对象计算出一个整数，称为散列码。根据这些计算出来的整数(散列码)保存在对应的位置上！
在Java中，散列表用的是链表数组实现的，每个列表称之为桶。
一个桶上可能会遇到被占用的情况(hashCode散列码相同，就存储在同一个位置上)，这种情况是无法避免的，这种现象称之为：散列冲突
• 此时需要用该对象与桶上的对象进行比较，看看该对象是否存在桶子上了~如果存在，就不添加了，如果不存在则添加到桶子上
• 当然了，如果hashcode函数设计得足够好，桶的数目也足够，这种比较是很少的~
• 在JDK1.8中，桶满时会从链表变成平衡二叉树（红黑树，是弱平衡二叉树）
如果散列表太满，是需要对散列表再散列，创建一个桶数更多的散列表，并将原有的元素插入到新表中，丢弃原来的表~
• 装填因子(load factor)决定了何时对散列表再散列~
• 装填因子默认为0.75，如果表中超过了75%的位置已经填入了元素，那么这个表就会用双倍的桶数自动进行再散列

3.红黑树介绍（未完待续）

3.1各自应用场景：

3.2回顾二叉查找树

首先我们来回顾一下：利用二叉查找树的特性，我们一般来说可以很快地查找出对应的元素。
可是二叉查找树也有个例(最坏)的情况(线性)：
。。。。。

4.Map—>HashMap

4.1首先看看HashMap的顶部注释说了些什么：

4.2HashMap的属性：

我们知道Hash的底层是散列表，而在Java中散列表的实现是通过数组+链表的
数组+链表–>散列表
我们可以简单总结出HashMap：
• 键不允许重复，值允许重复
• HashMap 是一个最常用的Map,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。
• 无序
• HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;
• HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力。（非同步）
• 底层由散列表(哈希表)实现
• 初始容量和装载因子对HashMap影响挺大的，设置小了不好，设置大了也不好

4.3HashMap构造方法

HashMap的构造方法有4个：
步骤：

1. 判断初始大小是否合理
2. 如果超过，赋值最大值
3. 初始化装载因子
4. 返回一个大于输入参数且最近的2的整数次幂的数给threshold

可能会感到奇怪的是：为啥是将2的整数幂的数赋给threshold？
threshold这个成员变量是阈值，决定了是否要将散列表再散列。它的值应该是：capacity * load factor才对的。
其实这里仅仅是一个初始化，当创建哈希表的时候，它会重新赋值的：

4.4主要方法

1.put方法（HashMap的核心）

put方法

1. 计算了哈希值
2. 并对哈希值执行了异或运算

直接将key作为哈希值不就好了吗，做异或运算是干嘛用的？

我们是根据key的哈希值来保存在散列表中的，我们表默认的初始容量是16，要放到散列表中，就是0-15的位置上。也就是tab[i = (n - 1) & hash]。可以发现的是：在做&运算的时候，仅仅是后4位有效~那如果我们key的哈希值高位变化很大，低位变化很小。直接拿过去做&运算，这就会导致计算出来的Hash值相同的很多。

而设计者将key的哈希值的高位也做了运算(与高16位做异或运算，使得在做&运算时，此时的低位实际上是高位与低位的结合)，这就增加了随机性，减少了碰撞冲突的可能性！

接下来我们看看resize()方法，在初始化的时候要调用这个方法，当散列表元素大于capacity * load factor的时候也是调用resize()

2.get方法
3.remove方法

4.5HashMap与Hashtable对比

从存储结构和实现来讲基本上都是相同的。它和HashMap的最大的不同是它是线程安全的，另外它不允许key和value为null。Hashtable是个过时的集合类，不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换

4.6必备知识点再现

HashMap实现原理—散列

Hash哈希算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系。散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中地址。
当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子(load factor)来决定何时对散列表进行再散列。例如：如果负载因子0.75，当散列表中已经有75%位置已经放满，那么将进行再散列。
负载因子越高(越接近1.0)，内存的使用效率越高，元素的寻找时间越长。负载因子越低(越接近0.0)，元素的寻找时间越短，内存浪费越多。

何时需重写equals？
当一个类有自己特有的“逻辑相等”概念（不同于对象身份的概念）；
Object类仅仅提供了一个对引用的比较，如果两个引用不是同一个那就返回false，这是无法满足大多数对象比较的需要的，所以要覆盖；

使用 == 操作符检查实参是否为指向对象的引用” 用instanceof操作符检查实参是否为正确的类型，把实参转换到正确的类型；
对于该类中每一个“关键”域，检查实参中的域与当前对象中对应的域值是否匹配。

对于既不是float也不是double类型的基本类型的域，可以使用 == 操作符进行比较；对于对象引用类型的域，可以递归地调用所引用的对象的equals方法，对于float和double类型的域，先转换成int或long类型的值，然后使用==操作符比较；

当你编写完成了equals方法之后，应该问自己三个问题：它是否是对称的、传递的、一致的？ 如果答案是否定的，那么请找到 这些特性未能满足的原因，再修改equals方法的代码

equals()和hashCode()同时覆写
尤其强调当一个对象被当作键值（或索引）来使用的时候要重写这两个方法；
覆写equals后，两个不同实例可能在逻辑上相等，但是根据Object.hashCode方法却产生不同的散列码，违反“相等的对象必须具有相等的散列码”。
导致，当你用其中的一个作为键保存到hashMap、hasoTable或hashSet中，再以“相等的”找另 一个作为键值去查找他们的时候，则根本找不到

不同类型的hashCode取值
如果该域是布尔型的，计算（f？0：1）
如果是char,short,byte或int，计算(int)f
如果是long类型，计算（int）(f^(f>>>32))
如果是float类型，计算Float.floatToIntBits（f）
如果是double类型，计算Dobule.doubleToLongBits(f)
如果该域是一个对象引用，递归调用hashCode
如果该域是一个数组，则把每个元素当做单独的域来处理，对每个重要的元素计算一个散列码

4.7HashMap总结（重点）

在JDK8中HashMap的底层是：数组+链表(散列表)+红黑树

在散列表中有装载因子这么一个属性，当装载因子*初始容量小于散列表元素时，该散列表会再散列，扩容2倍！

装载因子的默认值是0.75，无论是初始大了还是初始小了对我们HashMap的性能都不好

• 装载因子初始值大了，可以减少散列表再散列(扩容的次数)，但同时会导致散列冲突的可能性变大(散列冲突也是耗性能的一个操作，要得操作链表(红黑树)！
• 装载因子初始值小了，可以减小散列冲突的可能性，但同时扩容的次数可能就会变多！
初始容量的默认值是16，它也一样，无论初始大了还是小了，对我们的HashMap都是有影响的：
• 初始容量过大，那么遍历时我们的速度就会受影响~
• 初始容量过小，散列表再散列(扩容的次数)可能就变得多，扩容也是一件非常耗费性能的一件事~

从源码上我们可以发现：HashMap并不是直接拿key的哈希值来用的，它会将key的哈希值的高16位进行异或操作，使得我们将元素放入哈希表的时候增加了一定的随机性。

还要值得注意的是：并不是桶子上有8位元素的时候它就能变成红黑树，它得同时满足我们的散列表容量大于64才行的~

5.Map—>LinkedHashMap

LinkedHashMap： 此实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。存储的数据是有序的。

调用的是HashMap构造方法
LinkedHashMap没有put方法，原来LinkedHashMap和HashMap的put方法是一样的！LinkedHashMap继承着HashMap，LinkedHashMap没有重写HashMap的put方法
所以，LinkedHashMap的put方法和HashMap是一样的。
当然了，在创建节点的时候，调用的是LinkedHashMap重写的方法

根据源码注释，我们可以分析出：

• 底层是散列表和双向链表
• 允许为null，不同步
• 插入的顺序是有序的(底层链表致使有序)
• 装载因子和初始容量对LinkedHashMap影响是很大的~
• 初始容量对遍历没有影响

5.1LinkedHashMap总结

LinkedHashMap比HashMap多了一个双向链表的维护，在数据结构而言它要复杂一些，阅读源码起来比较轻松一些，因为大多都由HashMap实现了…

阅读源码的时候我们会发现多态是无处不在的~子类用父类的方法，子类重写了父类的部分方法即可达到不一样的效果！

• 比如：LinkedHashMap并没有重写put方法，而put方法内部的newNode()方法重写了。LinkedHashMap调用父类的put方法，里面回调的是重写后的newNode()，从而达到目的！

LinkedHashMap可以设置两种遍历顺序：
• 访问顺序（access-ordered）
• 插入顺序（insertion-ordered）
• 默认是插入顺序的
对于访问顺序，它是LRU(最近最少使用)算法的实现，要使用它要么重写LinkedListMap的几个方法(removeEldestEntry(Map.Entry<K,V> eldest)和afterNodeInsertion(boolean evict))，要么是扩展成LRUMap来使用，不然设置为访问顺序（access-ordered）的用处不大~
LinkedHashMap遍历的是内部维护的双向链表，所以说初始容量对LinkedHashMap遍历是不受影响的

6.Map—>TreeMap

查看源码的注释：

• TreeMap实现了NavigableMap接口，而NavigableMap接口继承着SortedMap接口，致使我们的TreeMap是有序的！
• TreeMap有序是通过Comparator来进行比较的，如果comparator为null，那么就使用自然顺序
• TreeMap底层是红黑树，它方法的时间复杂度都不会太高:log(n)~
• 非同步
• 使用Comparator或者Comparable来比较key是否相等与排序的问题~