源码冲浪之HashMap

HashMap是我们最常用到的集合之一，是java非常典型的数据结构。学习它的源码是非常只有必要的，我们所要了解的并不仅仅是“HashMap不是线程安全的，HashTable是线程安全的，通过synchronized实现的。HashMap取值非常快”等等。

了解hashmap必须要先对hashmap的存储结构有个了解
复制代码

它是属于数组及链表相结合的存储结构。如上图 x轴为数组，y轴为链表。 数组存储方式在内存地址是连续大小固定，一旦分配无法被其他引用占用，查询迅速，时间复杂度O(1)，插入删除比较慢，时间复杂度为O(n)。 而链表存储方式则与数组相反，属于非连续性，大小非固定，插入及删除块，查询速度慢。 所以HashMap相对中庸。

1 HashMap的数据结构是啥？数据结构上存储的数据对象结构是啥？ HashMap是一个存储数据对象<封装了K,V属性的对象>的集合，而这个集合是数组+链表类型的数据结构。

2 根据源码来分析hashMap内部的精髓 hash算法如何保证散列均匀冲突的解决方式

谈到hash 通常我们jdk的equals在比较的时候就会使用hash算法，此算法会定位到对象的存储位置 具体hash的原理是： hash函数：找到存储过程 被重写的hashCode（key）

index=h=Hash(int hashCode)

(key.hashCode)&&length -1

length 2^n 通过h就可以找到数组下标的位置

例子如下： 2^4=16 length-1 =15 二进制为 01111 h返回的是 10101 数组上存储的位置为： 00101 【上下都是1才是1】

好处： 1 散列的范围被低位限制---》散列位置一定在我们的索引范围（即length-1）之内。 2 低位的0如果越多 代表我们散列的结果越固定。【想象一个若是非length-1就会发生 10000 低位0较多，导致散列结果几乎就是一致】，导致冲突越多，导致数组位置的利用率不高。

3 手写一个自己的hashmap集合

首先我们会写一个自己的接口 面向接口编程【接口内部只保留最基础的put及get方法，然后定义内部接口】

然后就是写自定义的hashMap来继承此接口

定义参数并且补充了Spring门面模式的构造【即可以传参，如果不传参的话调用此类上面定义好的参数】

书写put方法

其中注意的是扩容的方法及原理

获取数组下标的方法并且重写hash算法

定义内部类，重写·Entry类

然后就是写get方法

代码清单如下：

MyMap接口

package com.epoint.HashMap;



/**

 * ，面向接口编程

 * 

 * @author lulf

 *

 * @param <K>

 * @param <V>

 */

public interface MyMap<K, V> {

 // MyMap 基本功能是快速存

 public V put(K k, V v);



 // 快速取

 public V get(K k);



 // 定义一个内部的接口

 public interface Entry<K, V> {



  public K getKey();



  public V getValue();

 }



}`

myhashMap
`package com.epoint.HashMap;



import java.util.ArrayList;

import java.util.List;



public class MyHashMap<K, V> implements MyMap<K, V> {



 // 定义数组大小 16

 // 结合着下面的扩容因子来解释一波：假如数组用了 4 usesize/defaulLenth =4/16=0.25 即使用率<0.75,不会扩容

 private static int defaulLenth = 1 << 4;



 // 扩容标准 所使用的useSize / 数组长度 >0.75

 // defaulAddSizeFactor 过大 造成扩容概率变低 存储小 但是就是存与取的效率降低

 // 0.9 有限的数组长度空间位置内会形成链表 在存与取值中都必须进行大量的遍历和判断(逻辑)

 // 过小 内存使用比较多，使用率不高，造成浪费

 private static double defaulAddSizeFactor = 0.75;



 // 使用数组位置的总数

 private int useSize;



 // 定义Map 骨架 只要 数组之一 数组

 private Entry<K, V>[] table = null;



 // Spring 门面模式运用

 public MyHashMap() {

  this(defaulLenth, defaulAddSizeFactor);

 }



 public MyHashMap(int length, double defaulAddSizeFactor) {

  if (length < 0)

   throw new IllegalArgumentException("参数不能为负数" + length);

  if (defaulAddSizeFactor <= 0 || Double.isNaN(defaulAddSizeFactor)) {

   throw new IllegalArgumentException("扩容标准必须是大于0的数字" + defaulAddSizeFactor);

  }

  this.defaulLenth = length;

  this.defaulAddSizeFactor = defaulAddSizeFactor;

  table = new Entry[defaulLenth];

 }



 @Override

 public V put(K k, V v) {

  // 存储是判断是否需要扩容

  if (useSize > defaulAddSizeFactor * defaulLenth) {

   up2Size();

  }

  // 获取数组下标

  int index = getIndex(k, table.length);

  Entry<K, V> entry = table[index];

  // 判断这个entry是否为空，为空意味着未被散列到

  if (entry == null) {

   table[index] = new Entry(k, v, null);

   useSize++;

  } else if (entry != null) {

   // 形成了链表结构

   table[index] = new Entry(k, v, entry);

  }

  return table[index].getValue();

 }



 // 寻找数组的下标

 private int getIndex(K k, int length) {

  int m = length - 1;

  int index = hash(k.hashCode()) & m;

  return index;

 }



 // 自定义写自己的hash算法

 private int hash(int hashCode) {

  hashCode = hashCode ^ ((hashCode >>> 20) ^ (hashCode >>> 12));

  return hashCode ^ ((hashCode >>> 7) ^ (hashCode >>> 4));

 }



 // 扩容

 private void up2Size() {

  // 如何扩容，无非就是新建一个2倍空间的数组

  Entry<K, V>[] newTable = new Entry[2 * defaulLenth];

  // 老数组的内容拿到新数组中

  againHash(newTable);



 }



 // 将老数组内容散列到新数组中

 private void againHash(MyHashMap<K, V>.Entry<K, V>[] newTable) {

  List<Entry<K, V>> entryList = new ArrayList<MyHashMap<K, V>.Entry<K, V>>();

  // for循环 即老数组内容被全部遍历到了entryList中

  for (int i = 0; i < table.length; i++) {

   if (table[i] == null) {

    continue;

   }

   // 继续找存到数组上的entry对象

   foundEntryByNext(table[i], entryList);

  }

  // 设置entryList

  if (entryList.size() > 0) {

   useSize = 0;

   defaulLenth = 2 * defaulLenth;

   for (Entry<K, V> entry : entryList) {

    if (entry.next != null) {

     entry.next = null;

    }

    put(entry.getKey(), entry.getValue());

   }

  }



 }



 private void foundEntryByNext(MyHashMap<K, V>.Entry<K, V> entry, List<MyHashMap<K, V>.Entry<K, V>> entryList) {

  // 形成了链表结构

  if (entry != null && entry.next != null) {

   entryList.add(entry);

   // 递归，不断地一层层取存entry

   foundEntryByNext(entry.next, entryList);

  } else {

   // 没有链表的情况

   entryList.add(entry);

  }



 }



 public int getUseSize() {

  return useSize;

 }



 @Override

 public V get(K k) {

  // hashCode (new Person(10,'llf'))--->hash---getindex--->最终位置

  int index = getIndex(k, table.length);

  if (table[index] == null) {

   throw new NullPointerException();

  }

  return findByValueByEqualKey(k, table[index]);

 }



 private V findByValueByEqualKey(K k, MyHashMap<K, V>.Entry<K, V> entry) {

  if (k == entry.getKey() || k.equals(entry.getKey())) {

   return entry.getValue();

  } else if (entry.next != null) {

   return findByValueByEqualKey(k, entry.next);

  }

  return null;

 }



 // 创建一个内部存储的对象类型

 class Entry<K, V> implements MyMap.Entry<K, V> {

  K k;

  V v;

  // 指向那被this挤压辖区的Entry对象

  Entry<K, V> next;



  public Entry(K k, V v, Entry<K, V> next) {

   this.k = k;

   this.v = v;

   this.next = next;

  }



  @Override

  public K getKey() {

   return k;

  }



  @Override

  public V getValue() {

   return v;

  }

 }
 
}
复制代码