业内经常说的一句话是不要重复造轮子，但是有时候，只有自己造一个轮子了，才会深刻明白什么样的轮子适合山路，什么样的轮子适合平地！
我将会持续更新java基础知识，欢迎关注。
往期章节：
在上一章节中，我们讲了集合框架的Collection部分，下面我们来讲一下Map接口
我们再看一下集合框架的结构图
map接口的实现类大致有 HashMap、LinkedHahMap、TreeMap、HashTable 四类。
Map
从这个名字上我们可以知道是“地图、映射”的意思。
map集合使用键(key)值(value)来保存数据，其中值(value)可以重复，但键(key)必须是唯一，也可以为空，但最多只能有一个key为空。
HashMap
对于hashMap，我们需要从名字中的hash入手，去分析他，hash，我们经常叫做哈希表又或者叫做散列函数。
在 JDK 中，Object 的 hashcode 方法是本地方法，也就是用 c 语言或 c++ 实现的，该方法直接返回对象的 内存地址。
先看一张图
如上图中的结构过程整个形成过程大致如下：
1，假如我们先插入一个键值对，然后进行hash后，存放在了数组的1号位置；
2，然后我们再插入一个键值对 ，经过hash后，存在了4号位置,；
3，再然后我们又插入了一个键值对，这个时候很不幸，与1号位置冲突，然后这个时候会在1号位置之后追加一个链表，让1号位置的Entry中的next指向这次最新追加的这一个键值对，以此类推；
从上图中我们大概可以了解到，整个的HashMap的数据结构就是 数组+链表（在jdk1.8中确切的说是Node对象，只不过Node实现了Entry接口），我们先看看Node 类的代码：
从上面的代码我们可以看出主要有4个属性，key value、 hash、以及再包含一个自身的类对象Node~ 这部分其实和我们上一节讲过的LinkedList的数据结构很像
当我们在代码中我们会调用put方法，源码如下：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
从注释中我们可以了解大意：“关联一个指定的值和键在这个map 如果map显然已经包含了这个键的映射，那么旧值就会被替代”
在这个代码中继续调用putval方法，我们继续看源码：
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
从注释中我们可以知道：实现map.put 和相关的方法
从第14行代码开始意思是，这个map如果是空的，那先初始化一个数组，然后再new一个 Node对象，放入数组中，具体的位置根据数组的长度和hash的 “与” 值确定 ；
如果已经有元素存在map中，则代码从19行开始执行，对于这块大致意思就是，如果已经存在相同的hashcode ，那么会判断键是否相同，如果也相同则替换原有的值。
另外关于hashMap的扩容，我们需要了解的是默认的容量是16 重载因子是0.75 什么意思呢？
就是说当集合中的数据量大小达到了门限值 16*0.75=12，那再添加元素进去，就会对当前的集合进行扩容，扩容为原来的2倍。
注意，这里是根据门限值进行扩容也就是12，而不是总容量16。
TreeMap
根据名字我们可以知道这是一个和树有关的map，关于treemap的结构图大致如下：
从上图中可以大概了解到，treemap的实现底层是红黑树，了解这个的同学相信也就能知道为什么treemap是有序的了。
这个图中的每一个节点对象都是Entry，他和hashmap中的不一样，而是一个类，不是接口，代码如下图所示：
从上图圈中可以了解到，每一个节点都包含 key、value、 以及Entry类型的 left、right、parent 属性
上述结构图形成过程大致描述如下：
1，我们先插入一个键值对，键为2；
2，再插入一个键为1，这个时候，会将这个键值对放在上一个的左子节点部分；
3，再插入一个3，这个时候，会将他放在第一个节点的右子节点部分；
4，如果再插入一个4，那这个时候，会把前面3个整体作为他的左子节点，以此类推；
我们再来看看源码：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
*
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
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;
}
从注释可以了解，和hashmap表达的意思一样，再看代码中，如果还没有初始化，那先进行初始化root节点，如果有指定比较器，那就根据指定的比较器，进行比较。
然后后面的代码就是根据插入的键进行大小的比较，然后设置各种左右子父节点属性等。
LinkedHahMap
关于linkedHashMap，从名字可以知道他是和链表有关系的，结构图如下所示：
注意图中的灰色箭头，在这里我们需要和一开始我们讲的hashmap中的结构图，做一个比较，在hashmap中虽然也有链表，但是我们要知道，那个链表只是为了解决hash冲突，链表中的元素互相之间没有什么关系，不代表谁早谁晚，或者说谁大谁小。
而这里的链表中比hashmap多了一个before 和after，如下图：
那么这里的before 和after就确定了插入的顺序先后。
HashTable
关于hashTable基本上和HashMap结构一致，不再赘述，唯一区别就是他是线程安全的，而且不允许null value，如果有直接抛出异常
为什么是线程安全的？我们看如下源码：
/**
* Maps the specified <code>key</code> to the specified
* <code>value</code> in this hashtable. Neither the key nor the
* value can be <code>null</code>. <p>
*
* The value can be retrieved by calling the <code>get</code> method
* with a key that is equal to the original key.
*
* @param key the hashtable key
* @param value the value
* @return the previous value of the specified key in this hashtable,
* or <code>null</code> if it did not have one
* @exception NullPointerException if the key or value is
* <code>null</code>
* @see Object#equals(Object)
* @see #get(Object)
*/
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
} // Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
} addEntry(hash, key, value, index);
return null;
}
从上面的方法中加上的 synchronized 关键词，我们就可以知道了。
另外要注意的是hashTable已经不建议使用了，取而代之的是ConcurrentHashMap ，因为他既保证了线程的安全性，又进一步提高了，效率。
四个实现类的异同：
1. HashMap是基于哈希表(hash table)实现，其keys和values都没有顺序。
2. TreeMap是基于红黑树(red-black tree)实现，按照keys排序元素，可以指定排序规则，如果不指定则按照自然排序。
3. LinkedHashMap是基于哈希表(hash table)实现，按照插入顺序排序元素。
4. Hashtable区别与HashMap的地方只有，它是同步的(synchronized),因此性能较低些。为了性能，在线程安全的代码中，优先考虑使用HashMap。
Map的遍历
对于map的遍历大致有以下3种方式：
//第1种只遍历键或者值，通过加强for循环
for(String s1:map.keySet()){//遍历map的键
System.out.println("键key ："+s1);
}
for(String s2:map.values()){//遍历map的值
System.out.println("值value ："+s2);
} //第2种方式Map.Entry<String, String>的加强for循环遍历输出键key和值value
for(Map.Entry<String, String> entry : map.entrySet()){
System.out.println("键 key ："+entry.getKey()+" 值value ："+entry.getValue());
} //第3种Iterator遍历获取，然后获取到Map.Entry<String, String>，再得到getKey()和getValue()
Iterator<Map.Entry<String, String>> it=map.entrySet().iterator();
while(it.hasNext()){
Map.Entry<String, String> entry=it.next();
System.out.println("键key ："+entry.getKey()+" value ："+entry.getValue());
}
比较器
在这里说以下Comparable 、 Comparator 2个接口
Comparable
只有一个方法compareto，而且是通过返回的int型数值判断大小
1、比较者大于被比较者（也就是compareTo方法里面的对象），那么返回正整数
2、比较者等于被比较者，那么返回0
3、比较者小于被比较者，那么返回负整数
Comparator
Comparator接口里面有一个compare方法，方法有两个参数T o1和T o2，是泛型的表示方式，分别表示待比较的两个对象，方法返回值和Comparable接口一样是int，有三种情况：
1、o1大于o2，返回正整数
2、o1等于o2，返回0
3、o1小于o3，返回负整数
二者之间的区别：
1，比较方法参数数不同；
2，后者接口中提供了更多的方法可以供使用；
3，前者只能和自己比较，后者可以对其他2个类进行比较；
关于集合部分，到这里我们就全部结束了。
注;以上源码分析都是基于jdk1.8
文中若有不正之处，欢迎批评指正！
