变强日记16

主要内容

1. redis的过期策略和内存淘汰机制
2. 算法：字符流中第一个不重复的字符

redis的过期策略和内存淘汰机制

redis的过期策略

redis给键值对设置的过期时间的命令主要有两种：

1
2

expire key 10 # 给制定的key设置过期时间为10秒
setex key 10 value # 给key的值设置为value，其过期时间为10秒

那么redis到底是如何处理这些过期的时间呢？
redis采用的定期删除和惰性删除的方式
定时删除：redis默认是每隔100ms就随机抽取一些设置了过期时间的key，检测是否过期，并进行处理。定时删除并不能保证所有已经过期的key都被删除。所以还需要惰性删除的机制。

惰性删除：是指在获取某个key的时候，redis会再次检测一下，这个key是否过期，如果过期了，这个时候就进行删除。

因此，如果定时删除漏掉了许多的key，且没有进行惰性删除，那么会怎么样？内存中堆积大量过期的key，导致redis的内存耗尽，就需要内存淘汰机制。

内存淘汰机制

如果redis的内存占用过多的时候，此时会进行内存淘汰，内存淘汰的策略主要有以下几种：
noeviction:当内存不足以容纳新写入的数据时，新写入操作报错。
allkey-lru:当内存不足以容纳新写入的数据时，在键空间中移除最近最少使用的key。（这个时最常见的）
allkey-random:当内存不足以容纳新写入的数据时，在键空间中随机移除某个key。
volatile-lru:当内存不足以容纳新写入的数据时,在设置了过期时间的键空间中，移除最近最少使用的key。
volatile-random:当内存不足以容纳新写入的数据时,在设置了过期时间的键空间中，随机移除某个key。
volatile-ttl:当内存不足以容纳新写入的数据时,在设置了过期时间的键空间中，有更早过期时间的key优先移除。

算法：字符流中第一个不重复的字符

题目：
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l“。

分析：使用一个map来记录目前字符出现的次数，一个来记录字符出现的次序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {
     int[] count=new int[256];
    int[] index=new int[256];
    int num=0;

    //Insert one char from stringstream
    public void Insert(char ch)
    {
        count[ch]++;
        index[ch]=num++;

    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
       int minIndex=num;
       char ch='#';
       for(int i=0;i<256;i++){
           if(count[i]==1&&index[i]<minIndex){
               ch=(char)i;
               minIndex=index[i];
           }
       }
       return ch;
    }

}