Hashmap HashMap继承AbstractMap类，实现了Map接口（由下图可见），在java集合中，它是一个基本的存储数据的结构。他的底层是由 数组+链表 构成，通过特定的哈希函数从 键（key）来定位值。
HashMap的结构形式大概如图所示： 构造哈希函数
1.直接寻址法 f(key) = key f(key) = a*key+y 2.除留余数法 f(x) = x%m
hash碰撞 m n f(m) = f(n) (m不等于n)
解决方式： 1.链地址法 2.探测发
hashmap的特点：
1、数据以key-value键值对形式存在 2、HashMap中键不能重复，即同一个key只能出现一次、若key相同，value会被覆盖 3、可以存在key为null的情况，value可以存在多个为null的情况 4、数据不能保证顺序性
hashmap的源码分析：
1.方法、属性、继承关系
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。继承关系：
extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable继承了AbstractMap抽象类，主要实现了map接口，当前HashMap也能实现克隆序列化Cloneable。
属性：
//HashMap的初始容量为16； static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //初始容量既可以传参给定，也可以给默认值，主要作用是对数据大小进行初始化，容量最大值 1<<30 static final int MAXIMUM_CAPACITY = 1 << 30; //加载因子：在扩容时使用（使用方法put），默认大小是0.75（loadFactor：用来计算threshold） static final float DEFAULT_LOAD_FACTOR = 0.75f; //底层存储数据，数组的数据类型是Entry static final Entry<?,?>[] EMPTY_TABLE = {}; //threshold扩容阈值：计算方式如上：容量*加载因子得到, 决定map是否需要扩容，threshold = capacity * loadFactor(hashmap的size的最大值) threshold = (int) Math.min(capacity * loadFactor) //Entry的数据类型包含存储的key——value数据，hash，还有entry类型的next属性，还可以看出entry数据是通过链表来组织连接 底层数据结构是：数组+链表 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash;2.CRUD
put添加元素的过程：
1.判断table是否为空数组，是则创建数组（注意：threshold值得改变） 2.key为null的添加操作做特殊处理，将该key对应的entry实体放入table[0]的位置（存在该key为null的实体进行覆盖操作） 3.过程通过key进行hash 4.通过indexfor方法来定位数据存储的索引位置 5.遍历该位置的链表，判断是否存在该key的实体(k.hashcode == equals)，有则将value替换 6.将该元素插入到对应的索引的链表 size 扩容（2*table.length）方式扩容（扩容时机） 插入位置（第一个位置，头插）
public V put(K key, V value) { //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16) if (table == EMPTY_TABLE) { inflateTable(threshold); } //如果key为null，存储位置为table[0]或table[0]的冲突链上 if (key == null) return putForNullKey(value); int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀 int i = indexFor(hash, table.length);//获取在table中的实际位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败 addEntry(hash, key, value, i);//具体的插入方法（扩容），头插法 return null; }remove删除元素的过程：
1、数组元素size为0，即不存在元素，直接返回 2、对key进行哈希，找到在数组table中的索引位置 3、对该位置的链表进行从头开始遍历 4、prev，e,next定义变量，找出key的位置 分两种情况： key对应的entry实体在链表头节点，直接将该节点的next的置为头结点 entry实体在链表中，该判断结点的后一个节点的next直接指向该节点的next节点
public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); } 通过key删除数据并且返回以前的值 final Entry<K,V> removeEntryForKey(Object key) { if (size == 0) { return null; } //先找到节点的位置，key == null（table[0]） 否则（hash（key）） int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; //如果要删除的节点是第一个只需要将第二个放入数组中就可以 if (prev == e) table[i] = next; else //如果不是就需要将前一个节点的next置于next prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; }get获取元素的过程：
get的过程是先计算hash然后通过hash与table.length取摸计算index值，然后遍历table[index]上的链表，直到找到key，然后返回 注意点： 什么情况返回null 1.先对key进行哈希，并找到key存在的数组table的索引位置 2.对索引位置的链表进行遍历，判断key是否相等（key的hashcode，==，equals）
public V get(Object key) { //如果key为null调用一个单独的方法,说明HashMap支持键为null if (key == null) return getForNullKey(); //先获取到Entry实体 Entry<K,V> entry = getEntry(key); //返回值 return null == entry ? null : entry.getValue(); } 通过键取值 getForNullKey private V getForNullKey() { if (size == 0) { return null; } //注意:null键所对应的实体在table[0]存储 for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }containsValue判断key是否存在方法
public boolean containsKey(Object key) { //直接调用getEntry看能不能找到对应的Entry实体即可 return getEntry(key) != null; } 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; }containsKey判断value是否存在方法
public boolean containsValue(Object value) { //特殊情况 if (value == null) return containsNullValue(); //查找是否为值为null的value //直接两层for循环遍历 Entry[] tab = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; }两者区别点： 1、判断相等方式不同：containsKey中key需要比较Hashcode、== equals containsValue中value直接equals 2、遍历数组大小不同：containsKey中通过key找到该key存在的数组索引位置，遍历该索引位置的链表即可 containsValue中需要对该链表所有数组的所有链表全部遍历
下面将根据HashMap的基本特性和属性实现一个简单的MyHashMap
/** * 描述：自己实现一个hashmap * @Author administrator{GINO ZHANG} * @Date2018/10/28 */ class myhashmap { private static int limit; //阈值，表示扩容时机，即当前数组链表长度是否到达阈值，到达即扩容 private int size; //元素个数 private int tableNum[]; //表示table上的每一个索引位置当前链表的数量个数 private Entry[] table; //entry类型的数组 class Entry { //entry类型的数组 private final Object key; private String value; private Entry next; public Entry(){ //无参构造函数 this.key = 0; this.value = null; this.next = next; } public Entry(Object key, String value, Entry next) { //带参构造函数 this.key = key; this.value = value; this.next = next; } /** * get,set方法 * @return */ public Object getKey() { return key; } public Object getValue() { return value; } public void setValue(String value) { this.value = value; } public Entry getNext() { return next; } public void setNext(Entry next) { this.next = next; } } public myhashmap(){ // myhashmap类的无参构造函数 this.table = new Entry[4]; this.size = 0; this.tableNum = tableNum; this.limit = table.length; } /** * 根据key的hashcode和table长度取模计算key在table中的位置 * @param key * @return */ public int hashCode(Object key) { return key.hashCode() % table.length; } public void put(Object key, String value) { int index = hashCode(key); //通过index方法计算key的hashCode，确定在数组中索引的位置 Entry entry = table[index]; //遍历index位置的entry，若找到重复key则覆盖对应entry的值，然后返回 while (entry != null) { //三种判断是否存在key实体的方法 if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) { entry.setValue(value); } entry = entry.getNext(); //在entry节点建立前驱next的联系 } //若index位置没有entry或者未找到重复的key，则将新key添加到table的index位置 add(index, key, value); size++; } private void add(int index, Object key, String value) { //将新的entry放到table的index位置第一个，若原来有值则以链表形式存放 Entry entry = new Entry(key, value, table[index]); table[index] = entry; //判断size是否达到扩容阈值，若达到则进行扩容 if (key.hashCode() >= limit) { resize(); } } /** * 扩容 * @param */ private void resize() { Entry[] newTable = new Entry[2*table.length]; //遍历原table，将每个entry都重新计算hash放入newTable中 for (int i = 0; i < table.length; i++) { Entry old = table[i]; while (old != null) { Entry next = old.getNext(); int index = hashCode(old.getKey()); old.setNext(newTable[index]); newTable[index] = old; old = next; } } //用newTable替table table = newTable; //修改临界值 limit = newTable.length; } /** * remove方法 * @param key */ public void remove(Object key) { int index = hashCode(key); //通过index方法计算key的hashCode，确定在数组中索引的位置 Entry prev = null; Entry entry = table[index]; while (entry != null) { if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) { if (prev == null) { table[index] = entry.getNext(); // } else{ prev.setNext(entry.getNext()); } //如果成功找到并删除，修改size size--; } prev = entry; entry = entry.getNext(); } } /**@Override public String toString() { return "myhashmap{" + "table=" + Arrays.toString(table) + '}'; }*/ @Override public String toString() { StringBuilder sb = new StringBuilder(); for (Entry entry : table) { while (entry != null) { sb.append(entry.getKey() + ":" + entry.getValue() + "\n"); entry = entry.getNext(); } } return sb.toString(); } public static void main(String[] args) { myhashmap hashMap = new myhashmap(); hashMap.put(0,"jiaruo"); hashMap.put(1,"Jenny"); hashMap.put(2,"Danny"); hashMap.put(3,"Corleone Z"); hashMap.put(4,"xiaoming"); hashMap.put(19,"xinan"); hashMap.remove(4); System.out.println(hashMap); System.out.println(hashMap.size); } }打印结果
C:\java\java7\jdk1.7.0_80\bin\java.exe -javaagent:D:\ideaIU-2018.1.5.win\lib\idea_rt.jar=5940:D:\ideaIU-2018.1.5.win\bin -Dfile.encoding=UTF-8 -classpath 0:jiaruo 1:Jenny 2:Danny 3:Corleone Z 19:xinan 5 Process finished with exit code 0