# demo

**Repository Path**: whiteandy/demo

## Basic Information

- **Project Name**: demo
- **Description**: 写的一些demo用例 
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-03-24
- **Last Updated**: 2021-04-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 1.LRU和LFU的实现

### LRU

- LRU (Least recently used) 最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。

  **LinkedHashMap简介**

  LinkedHashMap重写了HashMap的Node节点，在对象中添加了前后指针。这样在HashMap的数组中，有了链表（双向链表）的关系

  **LRU的实现**：

  LRU是通过jdk的容器LinkedHashMap实现。

  继承LinkedHashMap，初始化的时候将 accessOrder 置为true。 这样 在每次访问LinkedHashMap后，都会将新访问的数据放到链表的最后。

  重写removeEldestEntry的方法。达到最大值的时候，删除head节点。HashMap在添加数据的时候，留有扩展方法afterNodeInsertion。LinkedHashMap实现了afterNodeInsertion方法，通过removeEldestEntry方法判断是否要删除节点。

  hashMap扩展方法：

  ```
  void afterNodeAccess(Node<K,V> p) { }
  void afterNodeInsertion(boolean evict) { }
  void afterNodeRemoval(Node<K,V> p) { }
  ```

  

### LFU

 LFU(Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小。

**LFU的实现**

LFU中维护了一个 hashMap和数组。 hashMap用户hash映射获取数据。数组用于存储堆（小根堆）。访问次数使用堆排序。缓存满时，删除堆的第一个节点。

**堆**：

堆结构就是用数组实现的完全二叉树结构
2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4）堆结构的heapInsert与heapify操作
5）堆结构的增大和减少 
6）优先级队列结构，就是堆结构 

堆的孩子： 2n+1(左) 2n+2(右)
堆的父节点： (n-1)/2

**逻辑简介**

添加缓存的时候，校验缓存是否已经满了，满了删除堆的第一个节点。然后添加节点。

查询的时候，被查询的节点访问次数加一，调整该节点在堆中的排序

## 2幂计算

计算过程

a的n次幂。

n的二进制表示： 例如 n=6 二进制位 （0110）

a的6次幂为

​      

 a的 （2^3）(即a的8次幂)×（**0**）× a的 （2^2）(即a的4次幂)×（**1**） × a的（2^1）(即a的2次幂)*（**1**）×  a的（2^0）(即a的1次幂)*（**0**）=a的6次幂