咳咳深入理解是假的，话不多说，一起来研究一下！
HashMap
HashMap继承自AbstractMap,还包括map，cloneable等接口，如下：
public class HashMap<K,V> extends AbstractMap<K,V>
implements在这里插入代码片 Map<K,V>, Cloneable, Serializable {
这里要注意HashMap并没有继承Collection接口，它继承的接口也没有继承Iterable接口，这里要强调的是HashMap不能直接用foreach循环遍历，怎么遍历呢？下面会介绍。
我用的是jdk1.8，除了HashMap还有不少类继承自AbstractMap，HashSet等等，但是目前貌似HashMap用的最广泛，以前的实现都说设计不合理，不建议使用了。
继续，HashMap保存的数据是一个个key-value(键值)对，key是唯一的，value可以重复，注意如果插入了重复的key不会报错，但是会替换旧的value
Map<String, Integer> map = new HashMap<>(1024);
map.put("apple", 123);
map.put("pear", 456);
System.out.println(map.get("apple")); // 123
map.put("apple", 789); // 再次放入apple作为key，但value变为789
System.out.println(map.get("apple")); // 789
首先要注意HashMap是无序的也就是说不能像数组那样按照数据存放的顺序来获取数据，或者说不能通过索引获取数据，即使如此，HashMap存取数据的速度和List也不相上下，事实上，HashMap内部肯定也引用到了数组，但是前面说到HashMap是无序的，所以原理是，HashMap用hashcode来标记传入的每一个key，大部分的key对象都有一个唯一的hashcode，HashMap再通过这些hashcode映射到数组的索引，再通过索引就可以很快的获取value了。
粗略的分析一下HashMap的代码运作过程，配合代码更佳
先看看类变量
先看静态的，只展示我能理解的以及大部分时候必须用到的：
static final int ==DEFAULT_INITIAL_CAPACITY== = 1 << 4; 默认表容量
static final int ==MAXIMUM_CAPACITY== = 1 << 30; 最大表容量
static final float ==DEFAULT_LOAD_FACTOR== = 0.75f; 默认加载因子（机翻...）
然后再看一些实例变量：
transient Node<K,V>[] ==table==; 缓存表容量
transient int ==size==; map映射的数量
transient Set<Map.Entry<K,V>> ==entrySet==; kv集合
transient int ==modCount==; 修改计数器
int ==threshold==; 阈值，table的大小
final float ==loadFactor==; 加载因子
接下来就主要关注构造方法，put()，resize()
首先肯定是根据构造方法进行的初始化，注意初始过程并不会初始化table
一般只有初次调用put()的时候，会去调用resize(),产生一个空table实例，代码就不贴了，太复杂了，大概懂个流程就好，还有的情况是传入了一个Map对象会提前调用resize()产生table的实例。
调用resize()会判断table是否为空，如果为空确定新的数组容量等于阈值，而阈值会重新计算，==(int)(loadFactor*newtable.length)==代码里不是这么写的，意思是这么个意思，只要不超过最大值就等于这个值，只要初始化的阈值不是小于0，阈值就肯定会变(这里指的是值不指对象)，往后会不断乘二，容量也是，具体原因下面会分析。但是阈值并不是只有初始化table用到。
tips：在put()如果map映射数量大于阈值，就会调用resize()进行扩容！！！
哈希冲突
HashMap的方案听着很不错，但是这里有一个坑，如果不同对象的hashcode还是冲突了怎么办？就是传说中的哈希冲突，这时候HashMap的解决方案是将对应索引的数组元素变成一个链表，虽然hashcode冲突了，但是内容不冲突啊，通过equals迭代比较就可以获取value了，但是这样效率就很低了，因为这就得遍历链表再匹配内容，运行的时间就得由链表的长度说了算了，至于为什么不用数组而用链表，大概是因为无法预知需要的长度，而当映射的数量超过阈值的时候，再通过调用resize()进行扩容，数据量大的话，还是挺麻烦的。
我们也可以提前优化，会看上面的代码，我在初始化HashMap的时候传递了一个整数1024，意思是预备一个长度为1024的数组来存储kv，这里面做了什么呢？一起看看源码：
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
//static final float DEFAULT_LOAD_FACTOR = 0.75f;
}
主要分析这三个构造方法，但是并不止这三个
根据开发者的注释，默认容量是16
传入一个int后又调用了另一个构造方法，传入int以及一个静态的float常量，再看看这个构造方法做了什么，数据合法性检查，初始化常量loadFactor，回来再看又调用了一个tableSizeFor方法，继续
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
//static final int MAXIMUM_CAPACITY = 1 << 30;
}
这里涉及位操作，先回忆一下：
<< : 左移运算符，num << 1,相当于num乘以2 低位补0
>> : 右移运算符，num >> 1,相当于num除以2 高位补0
>>> : 无符号右移，忽略符号位，空位都以0补齐
% : 模运算 取余
^ : 位异或 第一个操作数的的第n位于第二个操作数的第n位相反，那么结果的第n为也为1，否则为0
& : 与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0
| : 或运算 第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1，那么结果的第n为也为1，否则为0
~ : 非运算 操作数的第n位为1，那么结果的第n位为0，反之，也就是取反运算（一元操作符：只操作一个数）
顺便回忆一下各运算符的执行顺序
- ()
- ! ~ ++ –
- * / %
- + -
- << >> >>>
- &
- |
- += -= *= /=
看到这里就大概了解这些就知道这个方法的作用了
上面的代码可以转换一下
n |= (n >>> 1);
n |= (n >>> 2);
n |= (n >>> 4);
n |= (n >>> 8);
n |= (n >>> 16);
这里其实也是一个安全检查不过这里是检查数组的长度，无论你输入的数是多少最终都会返回一个整数且这个数是2的n次方，注意最后有一个判断！最大值不会超过2的30次方，那么我输入的1024就还是1024咯，如果你输入了1000，那结果就变成是1024，因为你逃不过这个检查！然后最终确定通过resize()建立的数组长度。
总结：最好的办法就是大概预计数据的数量，提前设定合适的size
疑问：为什么非得要限制数组的长度为2的n次方？继续分析
继续分析源码
tab[i = (n - 1) & hash]
//这里映射了数组的索引
这是put方法的一截代码，为什么说一截？有兴趣的朋友可以现在就打开看看,嘿嘿
首先解释一下，tab是HashMap里面存储数据的数组，hash即使hashcode，n是数组长度，i就是个数据备份，上面的问题说到20条数据放入长度为16的数组，按照hashcode怎么处理呢，就是上面这样，这个有点类似MapReduce的分区操作，也可以类似的理解为求余，但是不同的是，位运算显然比求模运算快多了，但是这样处理有一点局限，就是数组的长度必须是2的n次方，我们先假设长度为16：
//(n-1) & hash
//补码：
0000 0000 0000 0000 0000 0000 0001 0000//16
0000 0000 0000 0000 0000 0000 0000 1111//(15-1)
//假设一个hash
0100 0100 0000 0010 1001 0100 0000 1001
//按位& 结果=9
0000 0000 0000 0000 0000 0000 0000 1001
//如果n是10，就是上面的结果是长度，那就不一样了，有4个位置它永远是空的因为两个1中间的两个0不管怎么&运算它都是0
另一个巧妙之处在于如果n等于2的n次方，减1之后的结果将是一串0挨着一串1，这样大大降低了哈希没有冲突但是缓存数组索引冲突带来的麻烦，应该不会有为什么不用 |(或) 的问题吧哈哈哈哈哈哈哈
其实除了主动扩容，HashMap内部的hash方法也可以一定程度上防止hash冲突
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这是HashMap内部计算hash的算法，就是一个异或运算和一个右移位运算，因为上面求索引使用的是位运算，所以，有些特殊情况可能因为位运算而出现
对象 A 的 hashCode 为
1000010001110001000001111000000
对象 B 的 hashCode 为
0111011100111000101000010100000
上面的情况用15&运算算出来都是0，>>>之后会把高位的数推到前面，一定程度上缓解了hash冲突的可能，但是还是会有特殊情况
对象 A 的 hashCode 为
1000010001110001000001111000000
对象 B 的 hashCode 为
100001000111000100100010011000
这样还是会冲突
空间换时间
这个是HashMap一个很重要的思想，我们知道空间复杂度和时间复杂度，如果哈希冲突导致形成链表，那即使是HashMap也回天乏术，只能用最原始的方法逐一遍历比较了，我们说会这样就会降低效率，因为本来时间复杂度为O(1)的指令突然变成O(n)了，效率固然就会下降，要回避这个问题就得回顾上面分析的缓存数组的长度的问题，如果长度足够长，每一个key都有它唯一的索引不冲突，那就不会形成链表，效率就大幅提升了，这里就可以留意到一个这样的想法：如果我的数组足够长，保证每个key都有唯一索引不就万事大吉了么！
这个想法不危险，大概就是空间换时间了，当然从上面的源码我们可以得知，容量最大也只有2的30次方，不会超过阈值，阈值最大是int最大值
内部链表
说到这里面的链表就太复杂了，笼统的概括一点吧。
从java1.8以后链表HashMap中的链表不再是单纯的链表，而是一个红黑树，当链表的长度大于8时就会进行树化(treeify)。
有空再专门看看这里面做的事。
equals()&hashcode()
除了空间换时间，还有就是优化我们的hashcode算法，当然你不需要修改java定义的hashcode算法，它非常健壮，但是你要给你自己写的类附加计算hashcode的算法！
public class main{
@Test
public void test(){
Map<Person,Integer> map2 = new HashMap<Person,Integer>();
map2.put(new Person("heyblack",12,12), 1);
map2.put(new Person("heyblack",123,123), 1);
System.out.println(map2.get(new Person("heyblack",12,12)));//null
}
}
class Person{
public String name;
public int age;
public double propety;
public Person(String name, int age, double propety) {
super();
this.name = name;
this.age = age;
this.propety = propety;
}
上面的Person类没有equals()hashcode()，所以会输出null，虽然他们不是同一个对象，但是他们的内容完全相等，理论上是可以得到结果的。如果key改成String类型或其他基本类型的包装类就不会有这样的问题，因为String以及各基本类型的包装类都有自己健壮的hashcode()和equals()，绝对不会有这样的问题，其实我的Person类也不是没有，我们继承了Object的，但是…我们不知道他怎么实现的hashcode也不需要知道，一看这代码。。。。
public native int hashCode();
public boolean equals(Object obj) {
return (this == obj);
}
这个Object的hashcode听说是内存地址，当然这不准确，但是基本可以确定计算出的hashcode应该是很健壮的，那调用get方法时通过hashcode计算出来的索引就非常可能不是我们想要的，所以我们要自己实现一个hashcode方法，也可以借助ide生成，还有equals，==是全等于运算符，在这里的意思是配对两者的指针是否指向常量池中同一实例对象，通俗的说就是存储的指针地址是否一致，显而易见不可能是一致的，所以HashMap认为他们不是同一个对象，这个时候如果你丢了put方法使用的对象，那你就没办法通过get享受HashMap的极速VIP通道了，只能遍历咯！所以修改一下
// 添加这两个方法
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
long temp;
temp = Double.doubleToLongBits(propety);
result = prime * result + (int) (temp ^ (temp >>> 32));
return result;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Person) {
Person p = (Person)obj;
return this.name.equals(p.name) && this.age == p.age;
}
return false;
}
使用HashMap要注意的问题大概就这么多了，但是可以继续研究一下hashcode的算法
hashcode算法
从String类的hashcode开始，看源码：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
value是String内部的char数组，hash是String的hashcode默认是0，计算过程就是不断的将字符数组的每一个字符转换为整数与31的积进行累加
ide生成的hashcode算法也是这样做的用字段与31的积累加，所以这里就有一个问题，为什么非得要用31，不用别的数
参考hashCode 为什么乘以 31
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)