go map时间复杂度

题目序号：(482)
题目来源： 腾讯
频次: 1

答案：阿纪、

1. map特性

   特性：kv存储，能在O(1)时间复杂度内找到v，
   实现： 存储： 对key进行hash，通过hash找到存储区域下标，存储到对应的数组位置。
         取值: 要先通过hash(key)得到下标位置，根据下标位置获得对应的value。
         底层是一个HashTable。

2. 为什么时间复杂度是O(1)
   hash函数：在程序启动时，会检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash
   key定位过程:

   以64位操作系统为例,key 经过哈希计算后得到哈希值，共 64 个 bit 位,计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位.
   如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。
   例如，现在有一个 key 经过哈希函数计算后，得到的哈希结果是：
   110010111 | 000011110110110010001111001010100010010110010101010 │ 01010
   用最后的 5 个 bit 位，也就是 01010，十进制的值为 10，也就是 10 号桶。这个操作实际上就是取余操作，但是取余开销太大，所以代码实现上用的位操作代替。
   再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，这是在寻找已有的 key。 
   最开始桶内还没有 key，新加入的 key 会找到第一个空位，放入。
   buckets 编号就是桶编号，当两个不同的 key 落在同一个桶中，也就是发生了哈希冲突。
   冲突的解决手段是用链表法：在 bucket 中，从前往后找到第一个空位。这样，在查找某个 key 时，先找到对应的桶，再去遍历 buck