Map集合 存储键值对，不能有重复的key，每一个key对应一个value；
散列表，是根据关键码值（key）进行访问的数据结构，也就是说，通过将key映射到表中一个位置来获取记录，加快查找的速度，这个映射函数叫做散列函数，存放记录的结构称之为散列表；寻址容易，插入删除也容易的数据结构； 链表的时间复杂度为O（N），二叉排序树的时间复杂度为O（log2 N） 散列表可以根据key来找到value，时间复杂度达到O（1） key采用hash函数来定位，通过hash函数可以得到散列码值； 通常以下几种方式构造哈希函数 （1）直接定址法：key address（key） = a*key+b； （2）平方取中法：给key值平方，取中间两位作为哈希函数的散了码 （3）折叠法：把key拆分为几部分，例如图书馆里的书，拆分为区域号-书架号-图书编号，这几个号码做一些运算作为散列码 （4）除留取余法：key作为被除数，hash表对应的最大长度m，取不大于m的质数作为除数，key%质数作为散列码；
如果哈希函数构造的不好，容易产生哈希冲突，使得时间复杂度从O（1）升为O（N）或更大。
（1）开放地址法：当插入元素且得到两个散列码相同时，第一个元素插入后，第二个元素插入到它后面的位置。 （2）链地址法：当插入元素且得到两个元素散列码相同时，第一个元素插入后，在这个元素的位置加入一个链表，插入第二个元素；hashmap采用链地址法解决hash冲突。
hashmap是基于哈希表非同步实现的，哈希表对应的接口是Map接口（非线程安全），我们可以通过key和hash函数得到散列码，从而定位位置，进行增删改查的操作。 jdk1.8之前，HashMap都是采用数组+链表实现的，即使用链地址法处理哈希冲突；不同的key值可能得到同样的散列码，同一Hash值的节点都存储在一个链表中，但是当链表中的元素越来越多的时候；通过key去查找的效率反而从O（1）~O（N）。jkd1.8中，HashMap采用数组+链表+红黑树的结构实现，当前链表的长度超过阈值8，将链表转换为红黑树，红黑树中的元素个数小于6，将红黑树再转换为链表。
hash算法直接使用源码中的hash算法，解决哈希冲突采用链地址法，即数组+链表实现，包括方法有put（K key，V value），get（K key），remove（K key）等方法 HashMap迭代器实现 （1）哈希表中数据分布是不连续的，在迭代器初始化的过程中必须先跳转到第一个非空数据节点 （2）当迭代器的下标到达当前桶的链表末尾时，迭代器下标跳转到下一个非空桶的第一个数据节点
class MyHashMap<K,V>{ private Node<K, V>[] table; private int size; class Node<K,V>{ protected K key; protected V value; protected int hash; protected Node<K, V> next; public Node(K key, V value, int hash) { this.key = key; this.value = value; this.hash = hash; } } public MyHashMap(int capacity){ table = new Node[capacity]; } public Iterator<Node<K, V>> iterator(){ return new Itr(); } class Itr implements Iterator<Node<K, V>>{ private int currentIndex;//当前桶的位置 private Node<K, V> nextNode;//返回的下一个数据节点 private Node<K, V> currentNode; //上一次next返回的数据节点 public Itr(){ if(MyHashMap.this.isEmpty()){ return; } for(int i=0; i < table.length; i++){ currentIndex = i; Node<K, V> firstNode = table[i]; if(firstNode != null){ nextNode = firstNode; return; } } } @Override public boolean hasNext() { return nextNode != null; } @Override public Node<K, V> next() { //返回下一个数据节点 currentNode = nextNode; //nextNode指向自己的next nextNode = nextNode.next; if(nextNode == null){ //说明当前桶的链表已经遍历完毕 //寻找下一个非空的桶 for(int i=currentIndex+1; i<MyHashMap.this.table.length; i++){ //设置当前桶位置 currentIndex = i; Node<K,V> firstNode = MyHashMap.this.table[currentIndex]; if(firstNode != null){ nextNode = firstNode; break; } } //nextNode保存的就是下一个非空的数据节点 } return currentNode; } @Override public void remove() { if(currentNode == null){ return; } K currentKey = currentNode.key; MyHashMap.this.remove(currentKey); currentNode = null; } } public void resize(){ //扩容桶table Node<K, V>[] newTable = new Node[table.length * 2]; for(int i=0; i<table.length; i++){ //将oldTable中每一个位置映射到newTable中 rehash(i, newTable); } this.table = newTable; } public void rehash(int index, Node<K,V>[] newTable){ Node<K, V> currentNode = table[index]; if(currentNode == null){ return; } Node<K, V> lowListHead = null; //低位的头 Node<K, V> lowListTail = null; //低位的尾 Node<K, V> highListHead = null; //高位的头 Node<K, V> highListTail = null; //高位的尾 //currentNode表示oleTable下index位置中当前节点 while(currentNode != null){ //当前节点在newTable中的位置 int newIndex = newTable.length-1 & hash(currentNode.key); if(newIndex == index){ //映射到原先下标处 if(lowListHead == null){ lowListHead = currentNode; lowListTail = currentNode; }else{ lowListTail.next = currentNode; lowListTail = lowListTail.next; } }else{ //newIndex与index不等，映射到高位下标处 if(highListHead == null){ highListHead = currentNode; highListTail = currentNode; }else{ highListTail.next = currentNode; highListTail = lowListTail.next; } } currentNode = currentNode.next; } //将lowList head->tail之前的节点链接到index位置 if(lowListTail != null){ newTable[index] = lowListHead; lowListHead.next = null; } //将highList head->tail之前的节点链接到index+table.length位置 if(highListTail != null){ newTable[index+this.table.length] = highListHead; highListHead.next = null; } } public int hash(Object key) { int h; return (h = key.hashCode()) ^ (h >>> 16); } public void put(K key, V value){ //确定所要添加元素的位置 int hash = hash(key);//散列码 int index = table.length-1 & hash;//确定的位置 //newNode -》table[index] == null || key在map不存在 //table[index]已经存在数据 //table[index]不存在数据 Node<K, V> firstNode = table[index];//得到该位置的第一个节点 if(firstNode == null){ table[index] = new Node(key, value, hash); size++; }else{ //第一种情况 key已经存在 考虑新值覆盖旧值 //第二种情况 key不存在 封装一个新的node尾插法插入链表 if(firstNode.key.equals(key)){ firstNode.value = value; //新值替换旧值 }else{ Node<K,V> tmp = firstNode; while(tmp.next != null && !tmp.key.equals(key)){ tmp = tmp.next; } if(tmp.next == null){ if(tmp.key.equals(key)){ tmp.value = value; //新值替换旧值 }else{ tmp.next = new Node(key, value, hash); size++; } }else{ tmp.value = value; } } } } public boolean remove(K key){ int hash = hash(key); int index = table.length-1 & hash; Node<K, V> firstNode = table[index]; if(firstNode == null){ return false; }else{ if(firstNode.next == null){ if(firstNode.key.equals(key) && firstNode.hash == hash){ //为什么判断key是否相等的同时还需要判断散列码 table[index] = null; return true; } } Node<K,V> tmpPrev = firstNode; Node<K, V> tmp = firstNode.next; while(tmp.next != null){ if(tmp.key.equals(key) && tmp.hash == hash){ //tmp之前节点的next指向tmp.next tmpPrev.next = tmp.next; size--; }else{ tmpPrev = tmp; tmp = tmp.next; } } } return false; } public Node<K,V> get(K key){ //获取对应key所在数组的index int hash = hash(key);//散列码 int index = table.length - 1 & hash; //定位key记录所在的位置 Node<K, V> firstNode = table[index]; if (firstNode == null) { return null; } if (hash == firstNode.hash && key == firstNode.key) { return firstNode; } else { //遍历链表 Node<K, V> currentNode = firstNode.next; while (currentNode != null) { if (currentNode.hash == hash && currentNode.key == key) { return currentNode; } currentNode = currentNode.next; } } return null; } public boolean isEmpty(){ return size == 0; } } public class TestDemo11 { public static void main(String[] args) { } }以putvalue为例
* static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 16 * static final int MAXIMUM_CAPACITY = 1 << 30; * static final float DEFAULT_LOAD_FACTOR = 0.75f; * static final int TREEIFY_THRESHOLD = 8; 桶上的节点个数大于8时会转为红黑树 * static final int UNTREEIFY_THRESHOLD = 6; 桶上的绩点个数小于6时会转为链表 * static final int MIN_TREEIFY_CAPACITY = 64; 桶中结构转化为红黑树对用的table的最小大小 * transient Node<K,V>[] table; 存储元素的数组 总是2的幂次方 * transient Set<Map.Entry<K,V>> entrySet; 哈希表中节点的集合 * transient int size; * transient int modCount; * int threshold; 临界值 * final float loadFactor; 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; }weakHashMap是特殊HashMap WeakHashMap的键关联的对象是弱引用对象
static class Entyr<K,V>extends WeakReference<Object>Entry 继承自WeakHashMapJava中四种引用 1.强引用 通过new出来对象所关联的引用称之为强引用，只要强引用存在，当前对象不会被回收 2.软引用 通过SoftReference类实现，在系统内存即将要溢出的时候，才会回收软引用对象 3.弱引用 通过WeakReference实现，只要发生垃圾回收，被弱引用关联的对象就会被回收掉 4.虚引用 通过PhantomReference实现，无法通过虚引用获取对象实例，唯一作用就是在这个对象被回收时，能够收到一个通知
