golang常用算法

1、Snowflake算法(分布式全局唯一id)

snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。

• 最高位是符号位，始终为0，不可用。
• 41位的时间序列，精确到毫秒级，41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。
• 10位的机器标识，10位的长度最多支持部署1024个节点。
• 12位的计数序列号，序列号即一系列的自增id，可以支持同一节点同一毫秒生成多个ID序号，12位的计数列号支持每个节点每毫秒产生4096个ID序号。

一毫秒生成4096个id，单秒4096000个id，任何平台都够用了。

2、LRU算法(最近最少使用算法)

在LRU算法中，使用了一种有趣的数据结构，称为哈希链表。我们知道哈希表是由多个<Key,Value>对组成的，哈希链表是将这写节点链接起来，每一个节点都有一个前驱结点和后驱节点，就像双向链表中的节点一样。哈希表拥有了固定的排列顺序。

golang中使用如下结构体实现

type LRUCache struct {
	Size          int // 节点的数量
	Cap          int // 容量
	Cache       map[interface{}]*Node
	Head, Tail *Node // 头尾节点
        lock          *sync.RWMutex
}