type LRU struct {
   data map[string]*list.Element
   cap int
   list *list.List
}

func (lru *LRU) add(k, v string) {
   if Map中存有這條Key {
      替換Map中的Value值
      將鏈表中的對應(yīng)節(jié)點移到最前面
   } else {
      if 已經(jīng)達到緩存容量上限 {
         獲取鏈表尾部節(jié)點的Key，并從Map中刪除
         移除鏈表尾部的Node
      }
      創(chuàng)建要插入的新節(jié)點
      將新節(jié)點插入到鏈表頭部
      放入Map中
   }
}
func (lru *LRU) get(k string) string {
   if Map中存有這條Key {
      返回查詢到的Value
      將對應(yīng)節(jié)點移動到鏈表頭部
   } else {
      返回 空
   }
}

//根據(jù)BloomFilter來思考一下我們需要什么
//一個bit圖，n個Hash函數(shù)
//一個BitMap的實現(xiàn)
type cmRow []byte //byte = uint8 = 0000，0000 = COUNTER 4BIT = 2 counter
//64 counter
//1 uint8 =  2counter
//32 uint8 = 64 counter
func newCmRow(numCounters int64) cmRow {
   return make(cmRow, numCounters/2)
}
func (r cmRow) get(n uint64) byte {
   return byte(r[n/2]>>((n&1)*4)) & 0x0f
}
0000,0000|0000,0000| 0000,0000 make([]byte, 3) = 6 counter
func (r cmRow) increment(n uint64) {
   //定位到第i個Counter
   i := n / 2 //r[i]
   //右移距離，偶數(shù)為0，奇數(shù)為4
   s := (n & 1) * 4
   //取前4Bit還是后4Bit
   v := (r[i] >> s) & 0x0f //0000, 1111
   //沒有超出最大計數(shù)時，計數(shù)+1
   if v < 15 {
      r[i] += 1 << s
   }
}
//cmRow 100,
//保鮮
func (r cmRow) reset() {
   // 計數(shù)減半
   for i := range r {
      r[i] = (r[i] >> 1) & 0x77 //0111，0111
   }
}
func (r cmRow) clear() {
   // 清空計數(shù)
   for i := range r {
      r[i] = 0
   }
}
//快速計算最接近x的二次冪的算法
//比如x=5，返回8
//x = 110，返回128
//2^n
//1000000 (n個0）
//01111111（n個1） + 1
// x = 1001010 = 1111111 + 1 =10000000 
func next2Power(x int64) int64 {
   x--
   x |= x >> 1 
   x |= x >> 2
   x |= x >> 4
   x |= x >> 8
   x |= x >> 16
   x |= x >> 32
   x++
   return x
}

//cmSketch封裝
const cmDepth = 4
type cmSketch struct {
   rows [cmDepth]cmRow
   seed [cmDepth]uint64
   mask uint64
}
//numCounter - 1 = next2Power() = 0111111(n個1）
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
func newCmSketch(numCounters int64) *cmSketch {
   if numCounters == 0 {
      panic("cmSketch: bad numCounters")
   }
   numCounters = next2Power(numCounters)
   sketch := &cmSketch{mask: uint64(numCounters - 1)}
   // Initialize rows of counters and seeds.
   source := rand.New(rand.NewSource(time.Now().UnixNano()))
   for i := 0; i < cmDepth; i++ {
      sketch.seed[i] = source.Uint64()
      sketch.rows[i] = newCmRow(numCounters)
   }
   return sketch
}
func (s *cmSketch) Increment(hashed uint64) {
   for i := range s.rows {
      s.rows[i].increment((hashed ^ s.seed[i]) & s.mask)
   }
}
// 找到最小的計數(shù)值
func (s *cmSketch) Estimate(hashed uint64) int64 {
   min := byte(255)
   for i := range s.rows {
      val := s.rows[i].get((hashed ^ s.seed[i]) & s.mask)
      if val < min {
         min = val
      }
   }
   return int64(min)
}
// 讓所有計數(shù)器都減半，保鮮機制
func (s *cmSketch) Reset() {
   for _, r := range s.rows {
      r.reset()
   }
}
// 清空所有計數(shù)器
func (s *cmSketch) Clear() {
   for _, r := range s.rows {
      r.clear()
   }
}