一、Map的实现类的结构
* |----Map:双列数据，存储key-value对的数据 ---类似于高中的函数：y = f(x)
* |----HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value
* |----LinkedHashMap:保证在遍历map元素时，可以按照添加的顺序实现遍历。
* 原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
* 对于频繁的遍历操作，此类执行效率高于HashMap。
* |----TreeMap:保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序
* 底层使用红黑树
* |----Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
* |----Properties:常用来处理配置文件。key和value都是String类型
*
*
* HashMap的底层：数组+链表 （jdk7及之前）
* 数组+链表+红黑树 （jdk 8）
二、Map结构的理解：
* Map中的key:无序的、不可重复的，使用Set存储所有的key
* ---> key所在的类要重写equals()和hashCode() （以HashMap为例）
*
* Map中的value:无序的、可重复的，使用Collection存储所有的value
* --->value所在的类要重写equals()
*
* 一个键值对：key-value构成了一个Entry对象。
* Map中的entry:无序的、不可重复的，使用Set存储所有的entry
常用方法
* 添加：put(Object key,Object value)
* 删除：remove(Object key)
* 修改：put(Object key,Object value)
* 查询：get(Object key)
* 长度：size()
* 遍历：keySet() / values() / entrySet()
三、Map实现类之一：HashMap
一、HashMap的数据结构就是用的链表散列，大概是怎么存储的呢？分两步
什么是链表散列呢？通过数组和链表结合在一起使用，就叫做链表散列。这其实就是hashmap存储的原理图。
1、HashMap内部有一个entry的内部类，其中有四个属性，我们要存储一个值，则需要一个key和一个value，存到map中就会先将key和value保存在这个Entry类创建的对象中。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; //就是我们说的map的key
V value; //value值，这两个都不陌生
Entry<K,V> next;//指向下一个entry对象
int hash;//通过key算过来的你hashcode值。
2、构造好了entry对象，然后将该对象放入数组中，如何存放就是这hashMap的精华所在了。大概的一个存放过程是：通过entry对象中的hash值来确定将该对象存放在数组中的哪个位置上，如果在这个位置上还有其他元素，则通过链表来存储这个元素。
3、HashMap存放元素的大概过程？
通过key、value封装成一个entry对象，然后通过key的值来计算该entry的hash值，通过entry的hash值和数组的长度length来计算出entry放在数组中的哪个位置上面，每次存放都是将entry放在第一个位置。在这个过程中，就是通过hash。
二、hashMap中的几个变量
1、loadFactor加载因子
loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，那么数组中存放的数据也就越稀，也就是可能数组中每个位置上就放一个元素。那有人说，就把loadFactor变为1最好吗，存的数据很多，但是这样会有一个问题，就是我们在通过key拿到我们的value时，是先通过key的hashcode值，找到对应数组中的位置，如果该位置中有很多元素，则需要通过equals来依次比较链表中的元素，拿到我们的value值，这样花费的性能就很高，如果能让数组上的每个位置尽量只有一个元素最好，我们就能直接得到value值了，所以有人又会说，那把loadFactor变得很小不就好了，但是如果变得太小，在数组中的位置就会太稀，也就是分散的太开，浪费很多空间，这样也不好，所以在hashMap中loadFactor的初始值就是0.75，一般情况下不需要更改它。
2、Size
size就是在该HashMap的实例中实际存储的元素的个数
3、threshold的作用？
threshold = capacity * loadFactor，当Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是衡量数组是否需要扩增的一个标准。注意这里说的是考虑，因为实际上要扩增数组，除了这个size>=threshold条件外，还需要另外一个条件，这个就等在源码中看吧。
4、什么是桶？
根据前面画的HashMap存储的数据结构图，你这样想，数组中每一个位置上都放有一个桶，每个桶里就是装一个链表，链表中可以有很多个元素(entry)，这就是桶的意思。也就相当于把元素都放在桶中。
5、capacity
这个就代表的数组的容量，也就是数组的长度，同时也是HashMap中桶的个数。默认值是16.
HashMap中put()
//添加元素
public V put(K key, V value) {
if (table == EMPTY_TABLE) {//判断是不是一个空的数组，也就是数组没有长度，通过构造方法创建，还没开始用，所以长度为0，这里就开始对数组进行增长。
inflateTable(threshold);//这个方法在第四个构造方法中介绍过，就是用来将数组变为大于等于threshold的2次幂。一开始threshold为16，那么根据算法，数组的开始长度也就是为16.
}
if (key == null)//这里可以看到，HashMap为什么可以使用null值了。
return putForNullKey(value);//将key为null的值存放到table中去。具体看下面putForNullKey的分析。
int hash = hash(key);//通过hash函数来将key转换为一个hash值
int i = indexFor(hash, table.length);//通过这个方法，将key转换来的hash值和数组的长度进行操作，得到在数组中的位置。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//在对应位置上加入新元素
Object k;
//遍历这个桶中的元素，看有没有相同的key值。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//只有相同的hash值并且 (可能key相同但是Key的hashcode不同也算key一样或者用equals比较得到相同)这说明里面有相同的key值。
V oldValue = e.value;//将老value用新value来替代。
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);//增加元素，方法内部实现很简单，就是将新增加的元素放第一位。而不是往后追加。
return null;
}
putForNullKey
//key为null的元素，默认放在table数组中的第一个位置上。并且可以知道，如果第一个位置上有元素，则将原来的值覆盖掉，如果第一个位置上没有entry。那么就将自己放在第一个位置。
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {//遍历在数组第一个位置上的链表的每个元素(entry)，其实就一个，因为null就一个。
if (e.key == null) {//如果发现有key为null的值，将现在的值赋值给原来key为null的value。
V oldValue = e.value;
e.value = value;
e.recordAccess(this);//一个空的方法。
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);//上面的情况是有key为null的元素。现在这里是没有key为null的元素，则要在第一个位置上放上自己。请看下面对这个方法的解析。
return null;
}
addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
//增加元素前，看一下元素的个数是否大于等于了我们规定存放在数组中的个数(threshold=数组容量*加载因子，只是一个存放判定数组是否需要扩增标准的变量)，并且在table这个指定位置上有元素，则对数组进行扩展
//前面一个条件成立，扩展数组，可以理解，为什么还要加上后面一个条件呢？原因是：我们希望尽量在每个数组的每个位置上只有一个元素是最好的，数组的容量是大于threshold的，也就是说size虽然到了要扩增的那个标准，
但是在数组中可能还是有很多位置上没有放元素，所以在这些位置上增加元素是合理的，不需要扩增。只有等到在size达到了扩增的标准并且添加元素的位置上有别的元素的情况下，才进行阔增。
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//扩增数组，看下面的分析。
hash = (null != key) ? hash(key) : 0;//扩增完数组后，原来的那些参数就没用了。需要重新计算，计算添加元素的hash值
bucketIndex = indexFor(hash, table.length);//通过hash值和数组的长度来计算出在数组中哪个位置
}
createEntry(hash, key, value, bucketIndex);//如果没有扩增，则直接用传过来的参数进行创建entry，很简单，将添加进入的元素放桶中的第一个元素，也就是数组对应位置就是该元素，然后把之后的元素给现在元素的next，具体可以看这个方法的源码，很简单
}
resize()
void resize(int newCapacity) {
Entry[] oldTable = table;//将老的数组存放在oldTable中
int oldCapacity = oldTable.length;//老的数组容量
if (oldCapacity == MAXIMUM_CAPACITY) {//判断老的容量
threshold = Integer.MAX_VALUE;//数组已经扩增到最大值了，所以将判定的标准增加到最大。
return;
}
Entry[] newTable = new Entry[newCapacity];//创建一个是原先两倍大小的数组。
transfer(newTable, initHashSeedAsNeeded(newCapacity));//因为新数组的长度改变了，所以每个元素在新数组中的位置也会改变，所以需要将每个元素的key得到的hashcode值重新算一遍，放入新数组中
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//这里就可以知道threshold的真正作用了，就是上面说的，作为判定是否需要扩增数组的一个标准。
}
transfer（）
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {//遍历老数组中的每一个桶，其实就是遍历数组的每一个位置。
while(null != e) {//遍历桶中的元素。e==null的情况是在一个桶中的最后一个元素的next为指向null，或者一开始这个桶就是空的。则需要遍历下一个桶。
Entry<K,V> next = e.next;//将e元素的下一个元素保存到next中。
if (rehash) {//
e.hash = null == e.key ? 0 : hash(e.key);//将每个元素的hash值算出来，通过的是每个元素的key，这个算法感兴趣的就点进去看。key和value为null的hash就为0，所以都在数组的第一个位置。
}
int i = indexFor(e.hash, newCapacity);//通过每个元素的hash值和所在数组的长度，计算出放在数组中哪个位置，这里就揭示了一开始我们的疑惑，不知道通过hash值怎么得到对应数组中的位置。
e.next = newTable[i];//每次在桶中添加新的数据，都是把新数据放在开头，旧数据放后面，这个桶就相当于是一个栈，先进去的就在最底层。
newTable[i] = e;//将自己放入数组中的对应位置
e = next;//桶中下一个元素。
}
}
}
indexFor()
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);//通过与运算，将h的二进制，和length-1的二进制进行与运算得出的结果就是数组中的位置。
}
经过这个方法，我们可以知道以下几点
1、构造方法中，并没有初始化数组的大小，数组在一开始就已经被创建了，构造方法只做两件事情，一个是初始化加载因子，另一个是用threshold记录下数组初始化的大小。注意是记录。
2、什么时候会扩增数组的大小？在put一个元素时先size>=threshold并且还要在对应数组位置上有元素，这才能扩增数组
3、对几个重要的方法的实现了解其作用，
putForNullKey：在put时，先判断可以是不是null值，是null值则用该方法进行处理
addEntry：增加元素的方法，其中会先判断是不是需要扩增数组，
不需要则调用createEntry()：将以拥有的四个属性创建entry，并且做添加元素的逻辑代码，在第一位添加，而不是在末尾追加
需要扩增调用resize()：这里面就是扩增的操作，将数组扩增为原来的两倍。扩增后，就需要使用transfer方法进行一些元素的移动，因为数组长度变化了，原来的元素就不会呆在原来的地方不动。
indexFor：算出元素在数组中的位置索引。
get(key)：通过key来找到对应的value值
//通过key获得value，知道了hashMap的原理后，其实这些都市大同小异。
public V get(Object key) {
if (key == null)//判断是否为null
return getForNullKey();//这个方法里太简单了，做两件事情，第一，如果size=0，返回null，反之到数组的第一个位置获取null对应的value值，前提是有，没有也返回null。
Entry<K,V> entry = getEntry(key);//通过key获得entry对象，看一下里面是如何获得的，我猜跟那个通过key删除元素差不多。也还是先找到对应位置，然后遍历链表。
return null == entry ? null : entry.getValue();//返回
}
getEntry
//和remove(key)这个方法的逻辑一样，但是简单得多，因为不用删除，只需要找到然后返回entry对象即可
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
接下来看一下hashMap的迭代器有哪些特别的没有？
发现四个迭代器内部类都市私有的，并没有什么特别，HashMap对象不支持直接调用迭代器，但是可以获得对象中所有的key集合(keySet)或者entrySet等，然后通过这些来调用迭代器获得自己所有的key或者entry对象或者value值。
/*
元视图操作的方法：
Set keySet()：返回所有key构成的Set集合
Collection values()：返回所有value构成的Collection集合
Set entrySet()：返回所有key-value对构成的Set集合
*/
@Test
public void test6() {
Map map = new HashMap();
map.put("AA", 123);
map.put(45, 1234);
map.put("BB", 56);
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()) {
Object obj = iterator1.next();
System.out.println(obj);
}
}
@Test
public void test5() {
Map map = new HashMap();
map.put("AA", 123);
map.put(45, 1234);
map.put("BB", 56);
//遍历所有的key集：keySet()
Set set = map.keySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println();
//遍历所有的value集：values()
Collection values = map.values();
for (Object obj : values) {
System.out.println(obj);
}
System.out.println();
//遍历所有的key-value
//方式一：entrySet()
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()) {
Object obj = iterator1.next();
//entrySet集合中的元素都是entry
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
System.out.println();
//方式二：
Set keySet = map.keySet();
Iterator iterator2 = keySet.iterator();
while (iterator2.hasNext()) {
Object key = iterator2.next();
Object value = map.get(key);
System.out.println(key + "=====" + value);
}
}
Map.Entry的使用
1.Map.Entry说明
Map是Java中的接口，Map提供了一些常用方法，如keySet()、entrySet()等方法。keySet()方法返回值是Map中key值的集合；entrySet()的返回值也是一个Set集合，此集合的类型为Map.Entry。
Map.Entry是Map的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value键值对）。接口中有getKey(),getValue方法。
2.Map.Entry的使用
你是否已经对每次从Map中取得关键字然后再取得响应的值感到厌倦？使用Map.Entry类，可以在同一时间得到所有的信息。
(1)标准的Map访问方法如下：
Set keys = map.keySet();
if(keys != null){
Iterator iterator = keys.iterator();
while (iterator.hasNext()){
Object key = iterator.next();
Object value = map.get(key);
}
}
这个访问方法有一个问题，从Map中取得关键字之后，必须每次重复返回Map中取得相对应的值，这是很繁琐和费时的。Map类提供了entrySet(),这个方法返回一个Map.Entry实例化后的对象集（Map.entrySet方法返回的是一个Set<Map.Entry<K,V>>,Map.Entry表示一个接口，它表示一个映射项（里面有key和value),而Set<Map.Entry<K,V>>表示一个映射项的Set集合)。接着，Map.Entry类提供了getKey()和getValue()。
(2)Map.Entry的使用
Set entries = map.entrySet( );
if(entries != null) {
Iterator iterator = entries.iterator( );
while(iterator.hasNext( )) {
Map.Entry entry =iterator.next( );
Object key = entry.getKey( );
Object value = entry.getValue();
}
}
提出问题
Entry类的作用是什么？？？
解决问题
我是一个静态类，实现Map.Entry< K ,V>,通过我可以构成一个单向链表，
在java帮助文档中没有我的地位，我只是一个内部类。
//源码privatestaticclassEntry<K,V>implementsMap.Entry<K,V>{inthash;finalKkey;Vvalue;//next 可构成单向链表Entry<K,V>next;protectedEntry(inthash,Kkey,Vvalue,Entry<K,V>next){this.hash=hash;this.key=key;this.value=value;this.next=next;}protectedObjectclone(){returnnewEntry<>(hash,key,value,(next==null?null:(Entry<K,V>)next.clone()));}// Map.Entry OpspublicKgetKey(){returnkey;}publicVgetValue(){returnvalue;}publicVsetValue(Vvalue){if(value==null)thrownewNullPointerException();VoldValue=this.value;this.value=value;returnoldValue;}publicbooleanequals(Objecto){if(!(oinstanceofMap.Entry))returnfalse;Map.Entry<?,?>e=(Map.Entry)o;returnkey.equals(e.getKey())&&value.equals(e.getValue());}publicinthashCode(){returnhash^value.hashCode();}publicStringtoString(){returnkey.toString()+"="+value.toString();}}
