hash

字典

扩容

Map实现原理分析

深度解密Go语言之 map

由浅到深，入门Go语言Map实现原理 golang map底层实现

哈希表

现在面试都这么直接的嘛？(golang map)

the core to design a map:

1. how to get hash value: hash funcitonn
2. how to handle collision.
3. how to rehash: grow,

hash function

what: 将输入数据经过一系列计算， 输出固定长度的数据

types:

1. 加密: 低碰撞，难复原
2. 非加密

why md5 is cryptographic:

1. one-way funciton
2. collision-resistant,

hash function excample

myhash:

1
2
3
4
5
6
7

func myHash(data []byte) uint32 {
  var hash uint32
  for _, b := range data {
    hash = hash*13 + uint32(b)
  }
  return hash
}

djb:

1
2
3
4
5
6
7
8

      func DJBHash(str string) uint {
        var hash uint = 5381
        for i := 0; i < len(str); i++ {
         hash = (hash << 5) + hash + uint(str[i])
        }
        return hash
      }
      

handle collision

1. open addressing；开放寻址法； 继续在原数组上探测一下空位置；

2. separate chaining；分离的链表

   使用额外的空间存储冲突；

   1. 链表;
   2. 树: 二叉树，红黑树;

rehash

grow

1. what? 填充度:load_factor= used_buceket/total_bucket 填充度太大或者太小的时候进行调整；

2. when? grow: 填充度 >=1; shrink: 填充度 <=0.1

3. how?

   创建两组字典；

   1. create h[1], h[1].buckets.len = h[2].buckets * 2
   2. 渐进式迁移
      1. set is hash = true
      2. rehashIndex++;
      3. rehashstep: 被动
      4. dictRehashMilliseconds:定时任务

shrink