发表于

为什么需要一致性哈希

首先介绍一下什么是哈希

Hash，一般翻译做散列，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

在分布式缓存服务中，经常需要对服务进行节点添加和删除操作，我们希望的是节点添加和删除操作尽量减少数据-节点之间的映射关系更新。

假如我们使用的是哈希取模( hash(key)%nodes ) 算法作为路由策略:

哈希取模的缺点在于如果有节点的删除和添加操作，对 hash(key)%nodes 结果影响范围太大了，造成大量的请求无法命中从而导致缓存数据被重新加载。

基于上面的缺点提出了一种新的算法：一致性哈希。一致性哈希可以实现节点删除和添加只会影响一小部分数据的映射关系，由于这个特性哈希算法也常常用于各种均衡器中实现系统流量的平滑迁移。

一致性哈希工作原理

首先对节点进行哈希计算，哈希值通常在 2^32-1 范围内。然后将 2^32-1 这个区间首尾连接抽象成一个环并将节点的哈希值映射到环上，当我们要查询 key 的目标节点时，同样的我们对 key 进行哈希计算，然后顺时针查找到的第一个节点就是目标节点。

根据原理我们分析一下节点添加和删除对数据范围的影响。

  1. 节点添加

只会影响新增节点与前一个节点（新增节点逆时针查找的第一个节点）之间的数据。
2. 节点删除

只会影响删除节点与前一个节点（删除节点逆时针查找的第一个节点）之间的数据。

这样就完了吗？还没有，试想一下假如环上的节点数量非常少，那么非常有可能造成数据分布不平衡，本质上是环上的区间分布粒度太粗。

怎么解决呢？不是粒度太粗吗？那就加入更多的节点，这就引出了一致性哈希的虚拟节点概念，虚拟节点的作用在于让环上的节点区间分布粒度变细。

一个真实节点对应多个虚拟节点，将虚拟节点的哈希值映射到环上，查询 key 的目标节点我们先查询虚拟节点再找到真实节点即可。

代码实现

基于上面的一致性哈希原理，我们可以提炼出一致性哈希的核心功能：

  1. 添加节点
  2. 删除节点
  3. 查询节点

我们来定义一下接口：

1
2
3
4
5
go复制代码ConsistentHash interface {
    Add(node Node)
    Get(key Node) Node
    Remove(node Node)
}

现实中不同的节点服务能力因硬件差异可能各不相同，于是我们希望在添加节点时可以指定权重。反应到一致性哈希当中所谓的权重意思就是我们希望 key 的目标节点命中概率比例，一个真实节点的虚拟节点数量多则意味着被命中概率高。

在接口定义中我们可以增加两个方法：支持指定虚拟节点数量添加节点，支持按权重添加。本质上最终都会反应到虚拟节点的数量不同导致概率分布差异。

指定权重时：实际虚拟节点数量 = 配置的虚拟节点 * weight/100

1
2
3
4
5
6
7
go复制代码ConsistentHash interface {
    Add(node Node)
    AddWithReplicas(node Node, replicas int)
    AddWithWeight(node Node, weight int)
    Get(key Node) Node
    Remove(node Node)
}

接下来考虑几个工程实现的问题：

  1. 虚拟节点如何存储？

很简单，用列表（切片）存储即可。
2. 虚拟节点 - 真实节点关系存储

map 即可。
3. 顺时针查询第一个虚拟节点如何实现

让虚拟节点列表保持有序，二分查找第一个比 hash(key) 大的 index，list[index] 即可。
4. 虚拟节点哈希时会有很小的概率出现冲突，如何处理呢？

冲突时意味着这一个虚拟节点会对应多个真实节点，map 中 value 存储真实节点数组，查询 key 的目标节点时对 nodes 取模。
5. 如何生成虚拟节点

基于虚拟节点数量配置 replicas，循环 replicas 次依次追加 i 字节 进行哈希计算。

go-zero 源码解析

core/hash/consistenthash.go

详细注释可查看：github.com/Ouyangan/go…

花了一天时间把 go-zero 源码一致性哈希源码看完，写的真好啊，各种细节都考虑到了。

go-zero 使用的哈希函数是 MurmurHash3，GitHub：github.com/spaolacci/m…

go-zero 并没有进行接口定义，没啥关系，直接看结构体 ConsistentHash：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
go复制代码// Func defines the hash method.
// 哈希函数
Func func(data []byte) uint64

// A ConsistentHash is a ring hash implementation.
// 一致性哈希
ConsistentHash struct {
    // 哈希函数
    hashFunc Func
    // 确定node的虚拟节点数量
    replicas int
    // 虚拟节点列表
    keys []uint64
    // 虚拟节点到物理节点的映射
    ring map[uint64][]interface{}
    // 物理节点映射，快速判断是否存在node
    nodes map[string]lang.PlaceholderType
    // 读写锁
    lock sync.RWMutex
}

key 和虚拟节点的哈希计算

在进行哈希前要先将 key 转换成 string

1
2
3
4
5
6
7
8
9
10
11
12
go复制代码// 可以理解为确定node字符串值的序列化方法
// 在遇到哈希冲突时需要重新对key进行哈希计算
// 为了减少冲突的概率前面追加了一个质数prime来减小冲突的概率
func innerRepr(v interface{}) string {
   return fmt.Sprintf("%d:%v", prime, v)
}

// 可以理解为确定node字符串值的序列化方法
// 如果让node强制实现String()会不会更好一些？
func repr(node interface{}) string {
   return mapping.Repr(node)
}

这里 mapping.Repr 里会判断 fmt.Stringer 接口，如果符合，就会调用其 String 方法。go-zero 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
go复制代码// Repr returns the string representation of v.
func Repr(v interface{}) string {
    if v == nil {
        return ""
    }

    // if func (v *Type) String() string, we can't use Elem()
    switch vt := v.(type) {
    case fmt.Stringer:
        return vt.String()
    }

    val := reflect.ValueOf(v)
    if val.Kind() == reflect.Ptr && !val.IsNil() {
        val = val.Elem()
    }

    return reprOfValue(val)
}

添加节点

最终调用的是 指定虚拟节点添加节点方法

1
2
3
4
go复制代码// 扩容操作，增加物理节点
func (h *ConsistentHash) Add(node interface{}) {
    h.AddWithReplicas(node, h.replicas)
}

添加节点 - 指定权重

最终调用的同样是 指定虚拟节点添加节点方法

1
2
3
4
5
6
7
go复制代码// 按权重添加节点
// 通过权重来计算方法因子，最终控制虚拟节点的数量
// 权重越高，虚拟节点数量越多
func (h *ConsistentHash) AddWithWeight(node interface{}, weight int) {
    replicas := h.replicas * weight / TopWeight
    h.AddWithReplicas(node, replicas)
}

添加节点 - 指定虚拟节点数量

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
29
30
31
32
go复制代码// 扩容操作，增加物理节点
func (h *ConsistentHash) AddWithReplicas(node interface{}, replicas int) {
    // 支持可重复添加
    // 先执行删除操作
    h.Remove(node)
    // 不能超过放大因子上限
    if replicas > h.replicas {
        replicas = h.replicas
    }
    // node key
    nodeRepr := repr(node)
    h.lock.Lock()
    defer h.lock.Unlock()
    // 添加node map映射
    h.addNode(nodeRepr)
    for i := 0; i < replicas; i++ {
        // 创建虚拟节点
        hash := h.hashFunc([]byte(nodeRepr + strconv.Itoa(i)))
        // 添加虚拟节点
        h.keys = append(h.keys, hash)
        // 映射虚拟节点-真实节点
        // 注意hashFunc可能会出现哈希冲突，所以采用的是追加操作
        // 虚拟节点-真实节点的映射对应的其实是个数组
        // 一个虚拟节点可能对应多个真实节点，当然概率非常小
        h.ring[hash] = append(h.ring[hash], node)
    }
    // 排序
    // 后面会使用二分查找虚拟节点
    sort.Slice(h.keys, func(i, j int) bool {
        return h.keys[i] < h.keys[j]
    })
}

删除节点

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
go复制代码// 删除物理节点
func (h *ConsistentHash) Remove(node interface{}) {
    // 节点的string
    nodeRepr := repr(node)
    // 并发安全
    h.lock.Lock()
    defer h.lock.Unlock()
    // 节点不存在
    if !h.containsNode(nodeRepr) {
        return
    }
    // 移除虚拟节点映射
    for i := 0; i < h.replicas; i++ {
        // 计算哈希值
        hash := h.hashFunc([]byte(nodeRepr + strconv.Itoa(i)))
        // 二分查找到第一个虚拟节点
        index := sort.Search(len(h.keys), func(i int) bool {
            return h.keys[i] >= hash
        })
        // 切片删除对应的元素
        if index < len(h.keys) && h.keys[index] == hash {
            // 定位到切片index之前的元素
            // 将index之后的元素（index+1）前移覆盖index
            h.keys = append(h.keys[:index], h.keys[index+1:]...)
        }
        // 虚拟节点删除映射
        h.removeRingNode(hash, nodeRepr)
    }
    // 删除真实节点
    h.removeNode(nodeRepr)
}

// 删除虚拟-真实节点映射关系
// hash - 虚拟节点
// nodeRepr - 真实节点
func (h *ConsistentHash) removeRingNode(hash uint64, nodeRepr string) {
    // map使用时应该校验一下
    if nodes, ok := h.ring[hash]; ok {
        // 新建一个空的切片,容量与nodes保持一致
        newNodes := nodes[:0]
        // 遍历nodes
        for _, x := range nodes {
            // 如果序列化值不相同，x是其他节点
            // 不能删除
            if repr(x) != nodeRepr {
                newNodes = append(newNodes, x)
            }
        }
        // 剩余节点不为空则重新绑定映射关系
        if len(newNodes) > 0 {
            h.ring[hash] = newNodes
        } else {
            // 否则删除即可
            delete(h.ring, hash)
        }
    }
}

查询节点

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
29
30
31
32
33
34
35
36
go复制代码// 根据v顺时针找到最近的虚拟节点
// 再通过虚拟节点映射找到真实节点
func (h *ConsistentHash) Get(v interface{}) (interface{}, bool) {
    h.lock.RLock()
    defer h.lock.RUnlock()
    // 当前没有物理节点
    if len(h.ring) == 0 {
        return nil, false
    }
    // 计算哈希值
    hash := h.hashFunc([]byte(repr(v)))
    // 二分查找
    // 因为每次添加节点后虚拟节点都会重新排序
    // 所以查询到的第一个节点就是我们的目标节点
    // 取余则可以实现环形列表效果，顺时针查找节点
    index := sort.Search(len(h.keys), func(i int) bool {
        return h.keys[i] >= hash
    }) % len(h.keys)
    // 虚拟节点->物理节点映射
    nodes := h.ring[h.keys[index]]
    switch len(nodes) {
    // 不存在真实节点
    case 0:
        return nil, false
    // 只有一个真实节点，直接返回
    case 1:
        return nodes[0], true
    // 存在多个真实节点意味这出现哈希冲突
    default:
        // 此时我们对v重新进行哈希计算
        // 对nodes长度取余得到一个新的index
        innerIndex := h.hashFunc([]byte(innerRepr(v)))
        pos := int(innerIndex % uint64(len(nodes)))
        return nodes[pos], true
    }
}

项目地址

github.com/zeromicro/g…

欢迎使用 go-zero 并 star 支持我们！

微信交流群

关注『微服务实践』公众号并点击 交流群 获取社区群二维码。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

Redis与分布式锁的问题已经是老生常谈了，本文尝试总结一些Redis、Zookeeper实现分布式锁的常用方案，并提供一些比较好的实践思路（基于Java）。不足之处，欢迎探讨。

Redis分布式锁

单机Redis下实现分布式锁

方案1：使用SET命令。

假如当前客户端需要占有一个user_lock的锁，它首次需要生成一个token（一个随机字符串，例如uiid），并使用该token进行加锁。

加锁命令：

1
2
shell复制代码redis> SET user_lock <token> EX 15 NX
OK

EX：该键会在指定时间后指定过期，单位为秒，类似参数还有PX、EXAT、PXAT。

NX：只有该键不存在的时候才会设置key的值。

所以如果user_lock键不存在，上面Redis命令会成功创建该Redis键，并设置该键在15秒后过期。

而其他客户端也使用该命令进行加锁，在这15秒时间内，其他客户端加锁失败（NX参数保证了该Redis键存在时命令执行失败）。

所以，当前客户端中锁定了user_lock，锁的有效时间为15秒。

为什么要使用token、有效期呢？有以下原因：

（1）锁的有效期可以保证不会发生死锁的情况。通常占有锁的客户端操作完成后需要释放锁（删除Redis键），使用锁有效期后，即使占有锁的客户端故障下线，15秒后锁也会自动失效，其他客户端就可以抢占该锁，不会出现死锁的情况。

（2）token的作用是防止客户端释放了不是自己占有的锁。如果不使用token，所以客户端都使用同一个值作为键user_lock的值，假如客户端A占有了锁user_lock，但由于过期时间到了，user_lock键被Redis服务器删除，这时客户端B占有了锁。而客户端A完成操作后，直接使用DEL命令删除当前user_lock键，这样客户端A就删除了非自己占有的锁。而为每个客户端分配一个token，并且客户端释放锁时需要检测该锁当前是否为自己所占有，即键user_lock的值是否为自己的token，如果是才可以删除该键，就可以避免该问题。

这里涉及两个命令，可以lua脚本保证原子性。如下面命令：

1
2
css复制代码> EVAL "if redis.call('GET',KEYS[1]) == ARGV[1] then return redis.call('DEL',KEYS[1]) else return 0 end" 1 user_lock <token>
(integer) 1

该方案可参考官方文档：redis.io/commands/se…

从上面内容可以看到，该方案的分布式锁并不是安全的，占有锁的客户端将在锁有效时间过后自动失去锁，这时其他客户端就可以占有该锁，这样将出现两个客户端同时占有一个锁的情况，分布式锁失效了。

所以，该方案锁的有效时间就非常重要，锁的有效时间设置过短，可能会出现分布式锁失效的情况，而有效时间设置过长，那么占有锁的客户端下线后，其他客户端仍然要无效等待较长时间才可以占有该锁，性能较差。

有没有更好一点的方案？我们看一下方案2。

方案2：自动延迟锁有效时间。

我们可以在一开始给锁设置一个较短的有效时间，并启动一个后台线程，在该锁失效前，主动延迟该锁的有效时间，

例如，在一开始时给锁设置有效时间为10秒，并启动一个后台线程，每隔9秒，就将锁的过期时间修改为当前时间10秒后。

示意代码如下：

1
2
3
4
5
6
7
8
scss复制代码new Thread(new Runnable() {
    public void run() {
        while(lockIsExist) {
            redis.call("EXPIRE user_lock 10");
            Thread.sleep(1000 * 9);
        }
    }
}).start();

这样就可以保证当前占用客户端的锁不会因为时间到期而失效，避免了分布式锁失效的问题，并且如果当前客户端故障下线，由于没有后台线程定时延迟锁有效时间，该锁也会很快自动失效。

提示；当前客户端释放锁的时候，需要停止该后台线程或者修改lockIsExist为false。

Java客户端Redisson提供了该方案，使用非常方便。

下面介绍一下如何使用Redisson实现Redis分布式锁。

（1）添加Redisson引用。

1
2
3
4
5
xml复制代码<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.16.4</version>
</dependency>

（2）使用示例如下：

1
2
3
4
5
6
7
8
9
10
11
ini复制代码Config config = new Config();
config.useSingleServer().setAddress("redis://localhost:6379");
RedissonClient redissonClient = Redisson.create(config);

RLock lock = redissonClient.getLock("user_lock");
lock.lock();
try {
// process...
} finally {
    lock.unlock();
}

如果没有特殊原因，建议直接使用Redisson提供的分布式锁。

但这种方式就一定安全吗？

大家考虑这样一种场景，假如获得锁的客户端因为CPU负载过高或者GC等原因，负责延迟锁过期时间的线程没法按时获得CPU去执行任务，则同样会出现锁失效的场景。

picture 2

该场景暂时没有比较好的处理方案，也不展开。

Sentinel、Cluster模式下实现分布式锁

实际生产环境中比较少使用单节点的Redis，通常会部署Sentinel、Cluster模型部署Redis集群，Redis在这两种模式下线实现分布式锁会有一个很麻烦的问题了。

为了保证高性能，Redis主从同步使用的是异步模式，就是说Redis主节点返回SET命令成功响应时，Redis从节点可能还没有同步该命令。

如果这时主节点故障下线了，那么就会出现以下情况：

（1）Sentinel、Cluster模式会选举一个从节点成为新主节点，而这个主节点是没有执行SET命令的。也就是说这时客户端并没有占有锁。

（2）客户端收到（之前主节点返回的）SET命令的成功响应，以为自己占有锁成功。

这时其他客户端也请求这个锁，也能占有这个锁，这时就会出现分布式锁失效的情况。

picture 3

出现这个情况的本质是Redis使用了异步复制的方式同步主从节点数据，并不严格保证主从节点数据的一致性。

对此，Redis作者提出了RedLock算法，大概方案是部署多个单独的Redis主节点，并将SET命令同时发送到多个节点，当收到半数以上Redis主节点返回成功后，则认为加锁成功。

这种机制感觉与分布式一致性算法（如Raft算法）中利用的“Quorum机制”基本一致吧。

关于该方案是否能真正保证分布式锁安全，Redis作者与另一位大佬Martin爆发了热烈的讨论，本文偏向实战内容，这里不一一展示RedLock算法细节。

即使该算法可以真正保证分布式锁安全，如果你要使用该方案，也很麻烦，需要另外部署多个Redis主节点，还需要支持该算法的可靠的客户端。考虑这些情况，如果在严格要求分布式锁安全的情况，使用ZooKeeper、Etcd等严格保证数据一致性的组件更合适。

Zookeeper分布式锁

Zookeeper由于保证集群数据一致，并自带Watch，客户端过期失效检测等机制，非常适合实现分布式锁。

Zookeeper实现分布式锁的方式很简单，客户端通过创建临时节点来锁定分布式锁，如果创建成功，则加锁成功，否则，说明该锁已经被其他客户端锁定，这时当前客户端监听该临时节点变化，如果该临时节点被删除，则可以再次尝试锁定该分布式锁。

虽然ZooKeeper实现分布锁的不同方案细节不同，但整体基本基于该方案进行扩展。

这里推荐使用Curator框架（Netflix提供的ZooKeeper客户端）实现分布式锁，非常方便。

下面介绍一下Curator的使用。

（1）引入Curator引用

1
2
3
4
5
6
7
8
9
10
11
xml复制代码<dependency>
    <groupId>org.apache.curator</groupId>
    <artifactId>curator-framework</artifactId>
    <version>3.3.0</version>
</dependency>

<dependency>
    <groupId>org.apache.curator</groupId>
    <artifactId>curator-recipes</artifactId>
    <version>3.3.0</version>
</dependency>

注意Curator版本与ZooKeeper版本对应。

（2）使用InterProcessMutex类实现分布式锁。

1
2
3
4
5
6
7
8
9
10
ini复制代码CuratorFramework client = CuratorFrameworkFactory.newClient("127.0.0.1:2181", 60000, 15000,
        new ExponentialBackoffRetry(1000, 3));
client.start();
InterProcessMutex lock = new InterProcessMutex(client, "/user_lock");
lock.acquire();
try {
    // process...
} finally {
    lock.release();
}

Curator支持多种分布式锁，非常全面：

  • InterProcessMutex：可重入排它锁，例子展示就是这种锁。
  • InterProcessSemaphoreMutex：不可重入排它锁。
  • InterProcessReadWriteLock：分布式读写锁。

使用方式也非常简单，这里不一一展开。

那么Zookeeper实现分布式锁一定安全吗？

假如客户端Client1在ZooKeeper中加锁成功，即成功创建了临时ZK节点，但Client1由于GC长时间没有响应ZooKeeper的心跳检测请求，ZooKeeper将Client1判断为失效，从而将临时ZK节点删除，这时客户端Client2请求加锁就可以成功加锁。那么这时就会出现Client1、Client2同时占有一个分布式锁，即分布式锁失效。

该场景与上面说的Redis延迟线程没有按时执行的场景有点类型，该场景展示也没有较好的解决方案。

虽然理论上ZooKeeper存在分布式锁失效的可能，但发生的概率应该比较，也可以通过增加ZooKeeper判断客户端的时间来减少这种场景，所以ZooKeeper分布式锁是可以满足绝大数要求分布式锁的场景的。

总结一下：

（1）如果不严格要求分布式锁安全，可以考虑在Sentinel、Cluster模式下使用redis实现分布式锁。例如多个客户端同时获取锁并不会导致严重的业务问题，或者只是要求性能优化避免多个客户端同时操作等场景，都可以使用Redisson提供的分布式锁。

（2）如果严格要求分布式锁安全，则可以使用ZooKeeper、Etcd等组件实现分布式锁。

当然，建议使用Redisson、Curator等成熟框架实现分布式锁，避免重复编码，也减少错误风险。

如需系统学习Redis，可参考作者新书《Redis核心原理与实践》。本书通过深入分析Redis 6.0源码，总结了Redis核心功能的设计与实现。通过阅读本书，读者可以深入理解Redis内部机制及最新特性，并学习到Redis相关的数据结构与算法、Unix编程、存储系统设计，分布式系统架构等一系列知识。

经过该书编辑同意，我会继续在个人技术公众号（binecy）发布书中部分章节内容，作为书的预览内容，欢迎大家查阅，谢谢。

语雀平台预览：《Redis核心原理与实践》

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战」。

前言

centos官方已经将停止Centos linux项目的更新和维护，并推出了Centos Stream项目(2024-05-31停更停维)

目前官网显示centos linux7的停维时间(2024-06-30),centos linux8的停维时间(2021-12-31)

但是对于目前在的现状，可能还有部分同学在用centos6，centos7。一但停更停维，补丁打不了，使用yum连软件都安装不了

具体官网详情: www.centos.org/centos-linu…
image.png

centos6

centos6停止维护的时间是2020-11-30,之后使用yum安装软件就会报相关仓库无法连接

如果此时还有老系统(centos6)需要更新，阿里云ECS的机器解决方案如下

默认CentOS-Base源

vim /etc/yum.repos.d/CentOS-Base.repo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
js复制代码[base]
name=CentOS-6.10
enabled=1
failovermethod=priority
baseurl=http://mirrors.cloud.aliyuncs.com/centos-vault/6.10/os/$basearch/
gpgcheck=1
gpgkey=http://mirrors.cloud.aliyuncs.com/centos-vault/RPM-GPG-KEY-CentOS-6

[updates]
name=CentOS-6.10
enabled=1
failovermethod=priority
baseurl=http://mirrors.cloud.aliyuncs.com/centos-vault/6.10/updates/$basearch/
gpgcheck=1
gpgkey=http://mirrors.cloud.aliyuncs.com/centos-vault/RPM-GPG-KEY-CentOS-6

[extras]
name=CentOS-6.10
enabled=1
failovermethod=priority
baseurl=http://mirrors.cloud.aliyuncs.com/centos-vault/6.10/extras/$basearch/
gpgcheck=1
gpgkey=http://mirrors.cloud.aliyuncs.com/centos-vault/RPM-GPG-KEY-CentOS-6

epel源

可能还有软件需要在epel源中，一样改一下配置
vim /etc/yum.repos.d/epel.repo

1
2
3
4
5
6
7
js复制代码[epel]
name=Extra Packages for Enterprise Linux 6 - $basearch
enabled=1
failovermethod=priority
baseurl=http://mirrors.cloud.aliyuncs.com/epel-archive/6/$basearch
gpgcheck=0
gpgkey=http://mirrors.cloud.aliyuncs.com/epel-archive/RPM-GPG-KEY-EPEL-6

这是因为阿里云自备了一个centos6.10的源，在急用时解决一下。

如果还有centos6的系统需要维护，最好的方式是自已搭建一个私有yum仓库，将软件同步好，以备不时之需

阿里云切源文档传送门:

help.aliyun.com/document_de…

centos7.1

按照网络博客将centos7.1的源切到某里源或某易源之后，过段时间这些源仓库都失效了

在使用yum安装软件时会报(Recv failure: Connection reset by peer)

但是比centos7.1更高的版本没有问题，此时需要 更换成centos默认源

默认CentOS-Base源

vim /etc/yum.repos.d/CentOS-Base源.repo

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
29
30
31
js复制代码[base]
name=CentOS-$releasever - Base
mirrorlist=http://mirrorlist.centos.org/?release=$releasever&arch=$basearch&repo=os&infra=$infra
#baseurl=http://mirror.centos.org/centos/$releasever/os/$basearch/
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-CentOS-7

#released updates 
[updates]
name=CentOS-$releasever - Updates
mirrorlist=http://mirrorlist.centos.org/?release=$releasever&arch=$basearch&repo=updates&infra=$infra
#baseurl=http://mirror.centos.org/centos/$releasever/updates/$basearch/
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-CentOS-7

#additional packages that may be useful
[extras]
name=CentOS-$releasever - Extras
mirrorlist=http://mirrorlist.centos.org/?release=$releasever&arch=$basearch&repo=extras&infra=$infra
#baseurl=http://mirror.centos.org/centos/$releasever/extras/$basearch/
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-CentOS-7

#additional packages that extend functionality of existing packages
[centosplus]
name=CentOS-$releasever - Plus
mirrorlist=http://mirrorlist.centos.org/?release=$releasever&arch=$basearch&repo=centosplus&infra=$infra
#baseurl=http://mirror.centos.org/centos/$releasever/centosplus/$basearch/
gpgcheck=1
enabled=0
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-CentOS-7

epel源

如果需要epel源，需要重新安装，因为epel源可能也是某里某易的

1
2
3
4
js复制代码#卸载epel源
yum remove epel-release
#安装epel源
yum install epel-release

在安装了centos自带的epel源(由mirrors.fedoraproject.org提供)后，再使用yum安装软件，依然报错:

image.png

解决方法: 将epel.repo配置文件中所有 行注释掉，然后将所有 行取消注释

最后正确的配置

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
js复制代码[epel]
name=Extra Packages for Enterprise Linux 7 - $basearch
baseurl=http://download.fedoraproject.org/pub/epel/7/$basearch
#metalink=https://mirrors.fedoraproject.org/metalink?repo=epel-7&arch=$basearch
failovermethod=priority
enabled=1
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-EPEL-7

[epel-debuginfo]
name=Extra Packages for Enterprise Linux 7 - $basearch - Debug
baseurl=http://download.fedoraproject.org/pub/epel/7/$basearch/debug
#metalink=https://mirrors.fedoraproject.org/metalink?repo=epel-debug-7&arch=$basearch
failovermethod=priority
enabled=0
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-EPEL-7
gpgcheck=1

[epel-source]
name=Extra Packages for Enterprise Linux 7 - $basearch - Source
baseurl=http://download.fedoraproject.org/pub/epel/7/SRPMS
#metalink=https://mirrors.fedoraproject.org/metalink?repo=epel-source-7&arch=$basearch
failovermethod=priority
enabled=0
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-EPEL-7
gpgcheck=1

Centos linux停更后如何应对

阿里云一篇文章对此进行了说明, 传送门: help.aliyun.com/document_de…

  • 在使用centos6的同学，已经EOL了，只能自力更生，没有条件创造条件
  • 在使用centos7的同学，于2024年6月30日EOL，还有时间可以早做准备
  • 在使用centos8的同学，目前有多个厂商在做这块的分支，包括国内厂商，可以先观望观望

操作系统EOL计划

阿里云文档列出了centos,ubuntu,Debian,Windows Server的这些操作系统已公布的停更，停维的日期

传送门: help.aliyun.com/document_de…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战」

相关文章

Java随笔记：Java随笔记

前言

  • 上篇文章没有介绍完所有的常用注解，今天来补充最后四个常用注解。
  • 还有一些其他的注解，感兴趣的小伙伴们可以自行研究了，在此笔者不在赘述了。
  • 平时我们在开发过程中，可以酌情使用。
  • 希望对你们有所帮助。
  • 不要嫌弃我水着分开发，为了更文活动，不寒碜！你懂得！

一、ApiResponse

  • @ApiResponse 用于方法上，说明接口响应的一些信息。

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    less复制代码@RestController
    @Api(tags = "Swagger测试类")
    public class SwaggerTestController {
        @ApiResponse(code = 200,message = "success", response = StudentResponse.class)
        @RequestMapping(value = "test-swagger",method = RequestMethod.GET)
        @ApiOperation(value = "查询学生详情",notes = "参数为id")
        public StudentResponse dyTest(){
            return new StudentResponse();
        }
    }

  • 效果如下：

  • image-20211129221220096.png

二、ApiResponses

  • 上面的只定义了200的状态码，如果是500呢？

  • @ApiResponses就是多个@ApiResponse组装起来。

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    less复制代码@RestController
    @Api(tags = "Swagger测试类")
    public class SwaggerTestController {
    //    @ApiResponse(code = 200,message = "success", response = StudentResponse.class)
        @ApiResponses({@ApiResponse(code = 200,message = "success", response = StudentResponse.class),
                @ApiResponse(code = 500,message = "failed", response = StudentResponse.class)})
        @RequestMapping(value = "test-swagger",method = RequestMethod.GET)
        @ApiOperation(value = "查询学生详情",notes = "参数为id")
        public StudentResponse dyTest(){
            return new StudentResponse();
        }
    }

  • 效果如下：

  • image-20211129221454085.png

三、ApiImplicitParam

  • 如果我们的参数较少的时候，比如，根据id查询指定数据详细信息的时候，我们总不能单独建个实体来描述吧？
  • 通常我们的做法时，五个参数以下时，可以通过ApiImplicitParam来对参数进行描述。
  • 当然，只限于Get请求，如果是添加、修改等操作，Post、Put请求时还是以实体类为主！

  • @ApiImplicitParam用于方法上，为单独的请求参数进行说明。

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    less复制代码@RestController
    @Api(tags = "Swagger测试类")
    public class SwaggerTestController {
        @ApiResponses({@ApiResponse(code = 200,message = "success", response = StudentResponse.class),
                @ApiResponse(code = 500,message = "failed", response = StudentResponse.class)})
        @RequestMapping(value = "test-swagger",method = RequestMethod.GET)
        @ApiOperation(value = "查询学生详情",notes = "参数为id")
        @ApiImplicitParam(name = "id", value = "学生ID", dataType = "string", paramType = "query", required = true, defaultValue = "1")
        public StudentResponse dyTest(String id){
            return new StudentResponse();
        }
    }

  • 效果如下：

  • image-20211129222607574.png

四、ApiImplicitParams

  • 多个参数时，ApiImplicitParam可能就满足不了我们的要求了，这时候需要组装下！

  • 同样的，多个@ApiImplicitParam组装起来。

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    less复制代码@RestController
    @Api(tags = "Swagger测试类")
    public class SwaggerTestController {
        @ApiResponses({@ApiResponse(code = 200,message = "success", response = StudentResponse.class),
                @ApiResponse(code = 500,message = "failed", response = StudentResponse.class)})
        @RequestMapping(value = "test-swagger",method = RequestMethod.GET)
        @ApiOperation(value = "查询学生详情",notes = "参数为id")
    //    @ApiImplicitParam(name = "id", value = "学生ID", dataType = "string", paramType = "query", required = true, defaultValue = "1")
        @ApiImplicitParams({@ApiImplicitParam(name = "id", value = "学生ID", dataType = "string", paramType = "query", required = true, defaultValue = "1"),
                @ApiImplicitParam(name = "name", value = "学生姓名", dataType = "string", paramType = "query", required = true, defaultValue = "1")})
        public StudentResponse dyTest(String id){
            return new StudentResponse();
        }
    }
    ​

  • 效果如下：

  • image-20211129222839545.png

总结

  • 到这里Swagger系列是真的结束了。再也没有东西可讲了。
  • 看完本系列的所有文章，相信你对Swagger有了相对来说比较深得了解了。
  • 希望对你有所帮助，本系列不说是全网最详细也差不多啦吧！
  • 哈哈哈，我可以整理了很多的才最终整合出来的！
  • 本系列文章都是个人见解，如有不对，敬请指出~
  • 轻喷！谢谢~

路漫漫其修远兮，吾必将上下求索~

如果你认为i博主写的不错！写作不易，请点赞、关注、评论给博主一个鼓励吧~hahah

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战。

FastAPI 有一个很大的亮点，那就是提供了一个简单易用，但是功能非常强大的依赖注入系统，使用依赖注入系统，我们可以轻而易举的把各种功能的组件集成到 FastAPI 应用中，接下来就一起来了解一下。

什么是依赖注入

所谓依赖注入，就是声明一些程序代码必须依赖的项，FastAPI 中称之为依赖项 dependencies，然后在实际运行中，FastAPI 会把所有的依赖项提供给有需要的程序，这个过程就是依赖注入。依赖注入非常适合在业务逻辑复用的场景使用，可以有效地减少代码重复，除此之外，在进行权限校验、身份验证、共享数据库连接等场景也非常适用。

使用依赖注入系统

简单使用

要是用依赖注入系统，首先需要创建依赖项，依赖项实际上是一个函数，如下：

1
2
3
4
5
6
7
8
9
10
python复制代码async def verify_token(request: Request):
    token = request.headers.get("token")
    if not token:
        raise HTTPException(
            status_code=HTTP_401_UNAUTHORIZED,
            detail="token 不正确"
        )
    # 验证、解析token，假设解析出user_id···
    user_id = 111
    return user_id

可见，声明依赖项和普通函数一样，可接收任意参数，返回任意信息。上面代码中，接收来自客户端的 request 对象并获取 header 中的 token，获取不到的话直接抛 HTTPException 异常（HTTPException 异常之后再介绍），会直接返回给客户端异常信息，获取到的话再对 token 进行验证、解析（例如JWT token 的解析），这里省略细节，假设解析出的 user_id 为111。

创建好依赖项之后，使用时在需要此依赖的路由函数的参数中使用Depends声明依赖，如下：

1
2
3
4
5
6
7
8
python复制代码@app.get("/get_info")
async def get_info(user_id: int = Depends(verify_token)):
    # 通过user_id获取用户信息
    user_info = {
        "user_id": user_id,
        "name": "tigeriaf"
    }
    return user_info

解释一下，上面的user_id: int = Depends(verify_token)对此接口声明了一个依赖Depends(verify_token)，那么当该接口被调用的时候，先调用此依赖项函数，传递合适的参数，依赖函数执行，返回结果再传递给路由函数的参数，如 user_id。

请求示例：

image.png
验证失败的请求结果：
image.png

可见，如果请求时不上送 token 信息，不会通过。

我们可以定义我们需要的任意依赖项，然后在需要的路由函数中声明使用。

把类当作被依赖对象

上面的依赖项是以函数的形式出现，其实 FastAPI 也支持以类的形式来创建依赖项。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
python复制代码class UserInfo:
    def __init__(self, request: Request):
        token = request.headers.get("token")
        if not token:
            raise HTTPException(
                status_code=HTTP_401_UNAUTHORIZED,
                detail="token 不正确"
            )
        # 验证、解析token，假设解析出user_id···
        self.user_id = 111
        self.name = "tigeriaf"


@app.get("/get_info")
async def get_info(user_info: UserInfo = Depends(UserInfo)):
    user_info = {
        "user_id": user_info.user_id,
        "name": user_info.name
    }
    return user_info

上面的 UserInfo 是一个类，当接口被调用的时候，类对象就会被初始化，返回类的实例 user_info，然后在路由函数内获取对象的相关属性。

多层嵌套依赖项

FastAPI 支持多层嵌套依赖项，可以根据需求创建创建有子依赖项的依赖项，深度不受限制，使用方法也非常简单，只需在依赖函数内使用Depends声明依赖即可，此处不作详细展开。

总结

除此之外，FastAPI 还支持路由声明多个依赖、使用 yield 关键字的依赖项等，总之，FastAPI 依赖注入系统非常强大，值得学习。

原创不易，如果小伙伴们觉得有帮助，麻烦点个赞再走呗~

最后，感谢女朋友在工作和生活中的包容、理解与支持 ！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

本文基于SpringBoot 2.5.7版本进行讲解

前文回顾：在上一篇文章，SpringBoot自动配置之AutoConfigurationImportSelector - SpringBoot自动配置(二)，讲到AutoConfigurationImportSelector的importSelector()方法通过调用getAutoConfigurationEntry()来获取需要自动配置的Bean信息。

但是，在第一篇文章，SpringBoot自动配置之@SpringBootApplication注解 - SpringBoot自动配置(一)，我也讲到其实SpringBoot并没有通过AutoConfigurationImportSelector类的importSelector()方法来获取自动配置的Bean信息。

有些读者，可能也在AutoConfigurationImportSelector类的selectImports()方法断点了，结果发生debug的时候，程序根本就没有进入到这个方法。

看到这里，我们心中必定是十万个为什么？

  1. AutoConfigurationImportSelector不是实现了ImportSelector接口吗？为什么selectImports()方法没有被调用？
  2. 既然Spring Boot不通过AutoConfigurationImportSelector的selectImports()方法来获取需要自动配置的Bean信息，那么从哪里获取？

别急，这就是本文讲解的内容。让我们带着这个问题，一起看下去吧。

配置调试环境

既然，程序没有调用AutoConfigurationImportSelector类的selectImports()方法。那么，我们就自己创建一个简单的ImportSelector接口的实现类，然后看看SpringBoot会不会调用这个自定义的ImportSelector实现类。

需要被注入的Bean：Hello

1
2
3
4
5
6
java复制代码public class Hello {

    public void print() {
        System.out.println("hello word");
    }
}

自定义ImportSelector实现类：HelloImportSelector

1
2
3
4
5
6
java复制代码public class HelloImportSelector implements ImportSelector {
    @Override
    public String[] selectImports(AnnotationMetadata importingClassMetadata) {
        return new String[] {"com.xgc.entity.Hello"};
    }
}

SpringBoot启动类：SpringTestApplication

1
2
3
4
5
6
7
8
java复制代码@Import(HelloImportSelector.class)
@SpringBootApplication
public class SpringTestApplication {

    public static void main(String[] args) {
        SpringApplication.run(SpringTestApplication.class, args);
    }
}

调试过程

到这里，就配置好了调试环境。接下来，我们在HelloImportSelector类的selectImports()方法打上断点，来看看程序会不会调用这个方法。

开始调试

image.png
看上图，我们知道SpringBoot程序是调用了selectImports()方法的。

追踪调用栈

既然，我们知道SpringBoot程序是会调用HelloImportSelector类的selectImports()方法，那么就好办了。

现在我们就沿着调用栈来一步一步追踪是哪里调用了这个selectImports()?

image.png

这里给出一部分调用栈的截图。我们看到,ConfigurationClassParser的processImports()方法调用了HelloImportSelector的selectImports方法。

那么接下来，我们就来看看这个processImports()方法做了什么吧。

ConfigurationClassParser类的processImports()方法

下面这里给出processImports()方法的定义和部分源码：

(我们不用去看这个方法的定义和部分源码，这里列出只是为了我后面解释的时候，读者能够翻来对照，读者可以直接跳过方法源码直接看文字部分。)

定义：

1
2
3
java复制代码private void processImports(ConfigurationClass configClass, SourceClass currentSourceClass,
      Collection<SourceClass> importCandidates, Predicate<String> exclusionFilter,
      boolean checkForCircularImports) {

部分源码：

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
29
30
31
32
33
34
35
36
kotlin复制代码for (SourceClass candidate : importCandidates) {
   if (candidate.isAssignable(ImportSelector.class)) {
      // Candidate class is an ImportSelector -> delegate to it to determine imports
      Class<?> candidateClass = candidate.loadClass();
      ImportSelector selector = ParserStrategyUtils.instantiateClass(candidateClass, ImportSelector.class,
            this.environment, this.resourceLoader, this.registry);
      Predicate<String> selectorFilter = selector.getExclusionFilter();
      if (selectorFilter != null) {
         exclusionFilter = exclusionFilter.or(selectorFilter);
      }
      if (selector instanceof DeferredImportSelector) {
         this.deferredImportSelectorHandler.handle(configClass, (DeferredImportSelector) selector);
      }
      else {
         String[] importClassNames = selector.selectImports(currentSourceClass.getMetadata());
         Collection<SourceClass> importSourceClasses = asSourceClasses(importClassNames, exclusionFilter);
         processImports(configClass, currentSourceClass, importSourceClasses, exclusionFilter, false);
      }
   }
   else if (candidate.isAssignable(ImportBeanDefinitionRegistrar.class)) {
      // Candidate class is an ImportBeanDefinitionRegistrar ->
      // delegate to it to register additional bean definitions
      Class<?> candidateClass = candidate.loadClass();
      ImportBeanDefinitionRegistrar registrar =
            ParserStrategyUtils.instantiateClass(candidateClass, ImportBeanDefinitionRegistrar.class,
                  this.environment, this.resourceLoader, this.registry);
      configClass.addImportBeanDefinitionRegistrar(registrar, currentSourceClass.getMetadata());
   }
   else {
      // Candidate class not an ImportSelector or ImportBeanDefinitionRegistrar ->
      // process it as an @Configuration class
      this.importStack.registerImport(
            currentSourceClass.getMetadata(), candidate.getMetadata().getClassName());
      processConfigurationClass(candidate.asConfigClass(configClass), exclusionFilter);
   }
}

这里就是文字部分了：

我们再精确点，看看是processImports()方法的那一部分代码调用了selectImports()方法。

1
2
3
4
5
6
7
8
9
java复制代码if (selector instanceof DeferredImportSelector) {
   this.deferredImportSelectorHandler.handle(configClass, (DeferredImportSelector) selector);
}
else {
   // 看这里，就是我调用了HelloImportSelector类的selectImports()方法
   String[] importClassNames = selector.selectImports(currentSourceClass.getMetadata());
   Collection<SourceClass> importSourceClasses = asSourceClasses(importClassNames, exclusionFilter);
   processImports(configClass, currentSourceClass, importSourceClasses, exclusionFilter, false);
}

看到这个if-else语句，相信大家都懂了。

AutoConfigurationImportSelector类的selectImports()方法没有被调用，而我们自定义的HelloImportSelector方法的selectImports()方法被调用的原因就是：
AutoConfigurationImportSelector实现了DeferredImportSelector接口。

简单讲讲ConfigurationClassParser的processImports()方法

现在我们翻回去看看刚刚上面贴出的processImports()的部分源码。
看代码的if-else语句判断部分就可以了。

processImports()方法会遍历importCandidates变量，然后判断里面的元素是否是ImportSelector或ImportBeanDefinitionRegistrar的实现类，否则就是@Configuration类来处理。

我们也能猜到importCandidates变量就是@Import(xxx)里面的xxx类。

这就是为什么@Import注解能够接收ImportSelector和ImportBeanDefinitionRegistrar实现类、@Configuration配置类以及普通的Bean对象，支持四种不同类型的类并完成Bean注入的原因。

对@Import注解不了解的读者，可以看Spring的@Import注解四种使用方式进行了解。

SpringBoot怎么获取需要自动配置的Bean信息？

看过SpringBoot自动配置之AutoConfigurationImportSelector - SpringBoot自动配置(二)的知道，AutoConfigurationImportSelector实现了DeferredImportSelector接口，而DeferredImportSelector接口又实现了ImportSelector接口，所以AutoConfigurationImportSelector接口还是实现了selectImports()方法。

在selectImports()方法中，我们又讲到selectImports()方法其实是通过调用getAutoConfigurationEntry()方法来拿到需要自动配置的bean信息。

既然我们在selectImports()方法断点发现SpringBoot并没有调用这个方法。那么我们不妨大胆猜想一下，SpringBoot最终会不会是直接通过调用getAutoConfigurationEntry()方法来获取需要自动配置的bean信息。

那么接下来，我们来求证一下。

image.png

可以看到SpringBoot确实是调用了这个方法来获取需要自动配置的bean信息。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第30天，活动详情查看：2021最后一次更文挑战

推荐阅读

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个纸箱某一个文件或目录的绝对路径字符串，返回更加简洁的规范路径。”

题目链接：

来源：力扣（LeetCode）

链接：71. 简化路径 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/‘ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//‘）都被视为单个斜杠 ‘/‘ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

  • 始终以斜杠 ‘/‘ 开头。
  • 两个目录名之间必须只有一个斜杠 ‘/‘ 。
  • 最后一个目录名（如果存在）不能 以 ‘/‘ 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘..’）。
    返回简化后得到的 规范路径 。
1
2
3
4
ini复制代码示例 1：
输入： path = "/home/"
输出： "/home"
解释： 注意，最后一个目录名后面没有斜杠。
1
2
3
4
ini复制代码示例 2：
输入： path = "/../"
输出： "/"
解释： 从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

二、解题

1、思路分析

这道题，先分析题意，给定一个路径，进行简化，有几种情况：

  • 多个连续/简化为一个/
  • 一个点.表示当前目录，去除
  • 两个点..表示上机目录，需返回上一级

当遇到两个点，需要返回上级目录，类似于弹出栈顶元素的操作。

遍历路径字符串，遇到/就跳过，遇到非斜杠，统计两个斜杠中间的.点数，一个点表示同级目录，跳过；

两个点标识上级目录，弹出栈顶元素。

当为其他字符串即为文件名时，直接入栈。

2、代码实现

代码参考：

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
29
30
31
32
33
34
35
36
37
38
39
40
csharp复制代码public class Solution {
    public string SimplifyPath(string path) {
            Stack<string> s = new Stack<string>();
            string[] spiltArr = path.Split('/');
            for (int i = 0; i < spiltArr.Length; i++)
            {
                if (spiltArr[i] == "")
                {
                    continue;
                }

                if (spiltArr[i] == "..")
                {
                    if (s.Count > 0)
                    {
                        s.Pop();
                    }
                }
                else if (spiltArr[i] != ".")
                {
                    s.Push(spiltArr[i]);
                }
            }

            if (s.Count != 0)
            {
                StringBuilder sb = new StringBuilder();
                while (s.Count != 0)
                {
                    sb.Insert(0, s.Pop());
                    sb.Insert(0, "/");
                }
                return sb.ToString();
            }
            else
            {
                return "/";
            }
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(n)

字符串中每个字符最多被遍历一次。

空间复杂度： O(n)

其中n代表字符串的长度。

三、总结

Linux的目录层级就是用栈实现的, 为了简单，直接使用字符串模拟栈的操作。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战」

  1. 结构体介绍

C语言里的结构体是可以包含不同数据类型和相同数据类型的一个有序集合，属于构造类型，可以自己任意组合，并且结构体里也可以使用结构体类型作为成员。

结构体在项目开发中使用非常多，无处不在，有了结构体类型就可以设计很多框架，模型，方便数据传输，存储等等。

结构体定义语法

1
2
3
4
5
6
7
8
9
10
cpp复制代码struct 结构体名称
{
    数据类型1 成员名1;
    数据类型2 成员名2;
    数据类型3 成员名3;
    .....
};

结构体的名称命名规则： 和普通变量命名规则一样—遵循C语言变量命名标准。
                       ‘A’~‘Z’ ‘a’~ ’z’  ‘0’~’9’  _

示例代码：

1
2
3
4
5
6
7
8
cpp复制代码struct app
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
};

上面这一块代码表示定义（声明）一个新的结构体类型。  数据类型名称：struct app
  1. 如何使用结构体定义变量？

结构体定义变量有3种形式：

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
29
30
31
32
33
34
35
cpp复制代码#include <stdio.h>

//第一种形式：在定义结构体类型的时候同时定义变量
struct app1
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
}a1,a2,a3;   //a1 a2 a3就是定义的结构体变量

//第二种形式
struct app2
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
};

//第三种形式: 匿名方式定义结构体
struct
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
}c1,c2,c3;  //c1 c2 c3就是定义的结构体变量

int main()
{
    //使用结构体类型定义变量
    struct app2 b1;
    struct app2 b2;
    struct app2 b3;

    return 0;
}
  1. 结构体的赋值

结构体变量的赋值语法：

1
cpp复制代码 结构体变量名.成员名=xxx;

结构体初始化赋值说明：

结构体只能在（定义结构体变量的时候）初始化的时候支持整体赋值，之后就只能按照成员单个赋值。

注意：结构体变量之间支持直接赋值。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
cpp复制代码#include <stdio.h>
#include <string.h>

//第一种形式：在定义结构体类型的时候同时定义变量
struct app1
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
}a1={23,"小白",5678},a2,a3={12,"小明",1234};   //a1 a2 a3就是定义的结构体变量

//第二种形式
struct app2
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
};

int main()
{
    //使用结构体类型定义变量
    struct app2 b1={15,"小李",6878};
    struct app2 b2;
    struct app2 b3;

    //单个修改结构体成员变量的值
    b1.age=18;
    //b1.name="555";
    strcpy(b1.name,"小丽");
   
    printf("b1:%d\n",b1.age);
    printf("b1:%s\n",b1.name);

    printf("a1:%d\n",a1.age);
    printf("a1:%s\n",a1.name);

    //结构体变量之间支持直接赋值 （要保证变量的类型要一致）。
   //int a=100;
   //int b;
   //b=a;
   b2=b1;  //将b1结构体变量赋值给b2结构体变量
   printf("b2:%d\n",b2.age);
   printf("b2:%s\n",b2.name);
    return 0;
}
  1. 结构体指针定义与使用

示例代码:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
cpp复制代码#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct app
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
}; 

int main()
{
    struct app a1;   //定义一个结构体变量
    struct app *p1;  //定义一个结构体指针
    struct app *p2;  //定义一个结构体指针
    p1=&a1;  //地址赋值  p1指向a1的空间

    //申请堆空间
    p2=malloc(sizeof(struct app));

    //通过指针访问成员
    p1->age=20;
    strcpy(p1->name,"小红");
    p1->number=1234;
    //输出数据
    printf("姓名:%s\n",p1->name);
    printf("学号:%d\n",p1->number);
    printf("年龄:%d\n",p1->age);

     //通过指针访问成员
    p2->age=13;
    strcpy(p2->name,"小李");
    p2->number=5678;
    //输出数据
    printf("姓名:%s\n",p2->name);
    printf("学号:%d\n",p2->number);
    printf("年龄:%d\n",p2->age);

    //释放空间
    free(p2);
    return 0;
}
  1. 结构体数组定义与使用

示例代码:

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
29
30
31
32
33
cpp复制代码#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct app
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
}; 

int main()
{
    
    //定义一个结构体数组
    struct app buff[10];  //一次定义了10个结构体变量
    struct app *p=buff;  //定义一个结构体指针

    //访问成员
    buff[0].age=10;
    strcpy(buff[0].name,"小米");
    buff[0].number=1234;

    //打印数据
    printf("姓名:%s\n",buff[0].name);
    printf("学号:%d\n",buff[0].number);
    printf("年龄:%d\n",buff[0].age);

    printf("姓名:%s\n",p[0].name);
    printf("学号:%d\n",p[0].number);
    printf("年龄:%d\n",p[0].age);
    return 0;
}
  1. 结构体当做函数的形参和返回值

示例代码：

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
29
30
31
32
33
34
35
36
37
38
cpp复制代码#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct app
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
}; 

struct app *func_stu(struct app *p);

int main()
{
    
    //定义一个结构体数组
    struct app buff[10];  //一次定义了10个结构体变量
   
    //调用函数
    func_stu(&buff[0]);

    //打印数据
    printf("姓名:%s\n",buff[0].name);
    printf("学号:%d\n",buff[0].number);
    printf("年龄:%d\n",buff[0].age);
    return 0;
}

//定义函数
struct app *func_stu(struct app *p)
{
   //访问成员
    p->age=10;
    strcpy(p->name,"小米");
    p->number=1234;
    return p;
}
  1. typedef关键字在结构体里使用方法
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
29
30
31
32
33
34
35
36
37
cpp复制代码#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct app
{
    int age; //年龄
    char name[100]; //姓名
    int number; //学号
}STU;  //STU叫结构体类型，相当于struct app的别名。  struct app == STU

STU *func_stu(STU *p);

int main()
{
    //定义一个结构体数组
    STU buff[10];  //一次定义了10个结构体变量
   
    //调用函数
    func_stu(&buff[0]);

    //打印数据
    printf("姓名:%s\n",buff[0].name);
    printf("学号:%d\n",buff[0].number);
    printf("年龄:%d\n",buff[0].age);
    return 0;
}

//定义函数
STU *func_stu(STU *p)
{
   //访问成员
    p->age=10;
    strcpy(p->name,"小米");
    p->number=1234;
    return p;
}
  1. 结构体位域

位域用的不多，但是也有地方使用，主要是节省空间。

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
29
30
31
32
33
34
cpp复制代码#include <stdio.h>
struct app
{
    unsigned int a:12;  //定义位域，指定位宽   12的单位是位
    unsigned int b:16;
    unsigned char c:1; //定义空间存储1位的数据。  1和0
    unsigned int :5;   //位域的名称可以省略掉,为了空间内存对齐而存在的
};
/*
1. 位域的大小不能超出本来数据类型大小。
2. 位域的名称可以省略掉,为了空间内存对齐而存在的
3. 位域的成员无法取地址操作
*/

int main()
{
    struct app data;
    //data.c=2;  错误 超出范围   只能存放0~1
    //data.b=65535;   错误 超出范围   只能存放0~65535
    // data.a=4096; 错误 超出范围   只能存放0~65535
    //printf("%d\n",data.c);
   // printf("%d\n",data.b);
    //printf("%d\n",data.a);

    //printf("%d\n",&data.a);   //错误 位域的成员无法取地址操作

    data.c=1;
    data.b=555; //只能存放0~65535
    data.a=888; //只能存放0~65535
    printf("%d\n",data.c);
    printf("%d\n",data.b);
    printf("%d\n",data.a);
    return 0;
}
  1. 结构体的内存对齐

9.1 示例1: 计算结构体内存对齐

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
cpp复制代码#include <stdio.h>
struct app
{
   int a1;
   char a2;
   char a3;
   char a4;
   char a5;
   char a6;
   char a7;
};
/*
目前32位系统里，使用的是gcc编译器。
开空间的对齐原理：以结构体里出现的最大数据类型的倍数开空间，最大是4个字节。
*/
int main()
{
    struct app data;
    printf("空间大小:%d 字节\n",sizeof(struct app)); //8
    return 0;
}

//func("1",1123,45,"45",123.45,'A');
void func(char *p,...)
{

}

9.2 示例2: 计算结构体内存对齐

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
cpp复制代码#include <stdio.h>
#if 0
struct app
{
   char a1;  //1
   short a2; //2
};
最终占用空间大小4个字节
#endif

#if 0
struct app
{
   int a1[10];   //4*10=40
   char a2[10];  //12
   int a3;      //4
   float a4;   //4
   char a5;   //4
};
//最终占用空间大小64个字节
#endif

#if 1
struct app
{
   int a1;
   double a2;
};
//最终占用空间大小64个字节
#endif

/*
目前32位系统里，使用的是gcc编译器。
开空间的对齐原理：以结构体里出现的最大数据类型的倍数开空间，最大是4个字节。
*/
int main()
{
    struct app data;
    printf("空间大小:%d 字节\n",sizeof(struct app)); //8
    return 0;
}

//func("1",1123,45,"45",123.45,'A');
void func(char *p,...)
{

}

9.3 输出结构体变量成员的地址，查看空间对齐情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
cpp复制代码#include <stdio.h>

struct app
{
   int a1[10];   //4*10=40
   char a2[10];  //12
   int a3;      //4
   float a4;   //4
   char a5;   //4
};
//最终占用空间大小64个字节

int main()
{
    struct app data;

    //输出地址   查看空间对齐原理
    printf("%#x\n",data.a1);
    printf("%#x\n",data.a2);
    printf("%#x\n",&data.a3);
    printf("%#x\n",&data.a4);
    printf("%#x\n",&data.a5);
    return 0;
}

9.4 对齐结构体进行强制对齐

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
cpp复制代码#include <stdio.h>

#pragma pack(1)  //1 2 4 8
struct app
{
   int a1[10];   //4*10=40
   char a2[10];  //1*10=10
   int a3;      //4
   float a4;   //4
   char a5;   //1
};

int main()
{
    struct app data;

    //输出地址   查看空间对齐原理
    printf("%#x\n",data.a1);
    printf("%#x\n",data.a2);
    printf("%#x\n",&data.a3);
    printf("%#x\n",&data.a4);
    printf("%#x\n",&data.a5);
    printf("%d\n",sizeof(struct app));
    return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第30天，活动详情查看：2021最后一次更文挑战

推荐阅读

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“假设你在爬楼梯，需要n阶到达楼顶，每次可以怕1到2阶，有多少种方法爬到楼顶呢。”

题目链接：

来源：力扣（LeetCode）

链接：70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意： 给定 n 是一个正整数。

1
2
3
4
5
6
markdown复制代码示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
1
2
3
4
5
6
7
markdown复制代码示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

二、解题

1、思路分析

看到求所有可能解，就可以想到用动态规划了。

爬第n阶楼梯的方法数量，等于 2 部分之和

  • 爬上 n-1n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
  • 爬上 n-2n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶

所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]

同时需要初始化 dp[0]=1 和 dp[1]=1

2、代码实现

代码参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
csharp复制代码public class Solution {
    public int ClimbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        int[] res=new int[n];
        res[0]=1;
        res[1]=2;
        for(int i=2;i<n;i++)
        {
            res[i]=res[i-1]+res[i-2];
        }
        return res[n-1];
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(n)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

这是一套很经典的动态规划的题目。

除了动态规划，还有很多有趣的解法。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战

题目描述

给你一个整数数组 nums 和一个整数 k。

如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ini复制代码示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

  • 今天的算法每日一题是统计优美子数组，题目给出了定义如果某个 连续 子数组中恰好有 k 个奇数数字。因此，我们只需要关注奇数即可。如何区分数字的奇偶性呢？我们只需要 num % 2 取余，偶数的余数是0，奇数的余数是1。
  • 题目要求返回请返回这个数组中「优美子数组」的数目。因此，我们只需要关注数目，不需要枚举每一个优美子数组。上一步，我们将 nums 转换为基偶数，降低了计算的复杂度。这里可以用前缀和的思想来统计，因为偶数的余数是0，奇数的余数是1。所以前缀和，统计的就是奇数出现的次数。实现代码如下

通过代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] S = new int[n + 1];
        S[0] = 0;
        for (int i = 1; i <= n; i++) {
            S[i] = S[i - 1] + nums[i - 1] % 2;
        }

        int ans = 0;
        
        int[] cnt = new int[n + 1];
        cnt[S[0]]++;
        for (int i = 1; i <= n; i++) {
            if (S[i] - k >= 0) {
                ans += cnt[S[i] - k];
            }
            cnt[S[i]]++;
        }

        return ans;
    }
}

总结

  • 上述算法的时间复杂度是O(n),空间复杂度是O(n)
  • 上面的思路大家都是清晰的，有同学对 cnt[] 这种缓存方式有疑问? 这里的 cnt[] 就是当缓存使用，我们常用的缓存是 map。cnt[] 一般是存储数字类的缓存，占用空间小，效率高。而 map 这种，缓存的 key 可以是数字，也可以是字符串，更加灵活一些。
  • 对于 cnt 这种用法，我们可以参考一个简单的题目，有效的字母异位词, 来帮助你理解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
java复制代码class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            cnt[t.charAt(i) - 'a']--;
            if (cnt[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}
  • 在有效的字母异位词题目中，cnt用来统计字符出现的次数。提升算法执行效率。
  • 坚持算法每日一题，加油！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%