一. 什么是hash表

在讨论 哈希表 之前，我们先来了解下其他数据结构的增删改查等基础操作的性能

　　数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找， 斐波那契 查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

　　线性链表：对于 链表 的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表，复杂度为O(n)

　　 二叉树 ：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

　　哈希表：在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。 比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作 。

哈希冲突

如果两个不同的元素，通过哈希散列操作得出的地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的 哈希冲突 ，也叫哈希碰撞。哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而 hashMap 即是采用了链地址法，也就是数组+链表的方式。

二.HashMap 数组+链表的实现原理

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。

数组存储区间是连续的，占用内存严重。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；

链表存储区间离散，占用内存比较宽松，空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。

下面用golang模拟了HashMap基本操作,性能有待优化

 package common

 const  (
   loadFactor = 0.75 //扩容因子
)

type HashMap  struct {
   m []*Entity // hash 表的桶
   len int //长度
    capacity  int //当前容量
}
type Entity struct{ //键值对
   key string
   value interface{}
   next *Entity
}

//初始化一个hashmap 容量
func NewHashMap(cap int) * Hash Map{
   if cap < 16 {
      cap = 16
   }
   hashMap := new(HashMap)
   hashMap.m = make([]*Entity,cap,cap)
   hashMap.capacity = cap
   return hashMap
}
func (h *HashMap)Index(key string) int{
   return BKDRHash(key, h.capacity) //计算键的哈希值
}

//写入一个键值对
func (h *HashMap)Put(key string, value interface{}) {
   index := h.Index(key)
   entity := h.m[index]
   if entity == nil { //该下标没有值，直接写入
      h.m[index] = &Entity{key,value, nil}
   }else{ //有值，找到最后一个节点
      for entity.next != nil {
         if entity.key == key { //如果是相同的键就进行修改操作
            entity.value = value
            return
         }
         entity = entity.next
      }
      entity.next = &Entity{key,value,nil}
   }
   h.len++
   if (float64(h.len)/float64(h.capacity)) > loadFactor { //扩容
      newHash :=  NewHashMap(2*h.capacity)
      for _,val := range h.m {//TODO 优化 理论上原数组只有一半的数据需要移动
         data := val
         if data != nil {
            newHash.Put(data.key,data.value)
         }
      }
      h.capacity = newHash.capacity
      h.m = newHash.m
   }
}

//获取
func (h *HashMap)Get(key string) interface{}{
   index := h.Index(key)
   entity := h.m[index]
   if entity == nil{
      return nil
   }
   if entity.key == key {
      return entity.value
   }
   for entity.next != nil {
      if entity.key == key {
         return entity.value
      }
      entity = entity.next
   }
   return nil
}
//删除
func (h *HashMap)Del(key string){
   index := h.Index(key)
   head := h.m[index]

   if head == nil{
      return
   }
   //如果是头结点
   if head.key == key {
      h.m[index]  = head.next
      return
   }
   curr := head
   //保存上一个节点
  var pre  *Entity
for curr != nil && curr.key != key{
if curr.next != nil && curr.next.key == key{
pre = curr
curr = curr.next
break
}
curr = curr.next
}
   if pre != nil{
      pre.next = curr.next
   }
}

func BKDRHash(str string, capacity int) int {
   seed := int(131) // 31 131 1313 13131 131313 etc..
   hash := int(0)
   for i := 0; i < len(str); i++ {
      hash = (hash * seed) + int(str[i])
   }
   return hash%capacity
}  

三.HashMap扩容机制

当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高，所以为了提高查询的效率，就要对hashmap的数组进行扩容，在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置。

那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。