字符串哈希（String Hashing）是一种将字符串映射成整数值的技术。它在解决字符串相关问题中非常有用，例如在计算不同字符串的数量、字符串匹配、模式匹配等问题中广泛应用。下面详细讲解字符串哈希的原理和用途：
**原理：**



1. 选择一个适当的基数（通常选择一个质数），如常用的 31 或 53。这个基数将作为哈希函数的参数，通常称为“质数模”。
2. 对字符串中的每个字符，将其转化为一个整数值（例如，字符 'a' 可以映射为 0，'b' 可以映射为 1，依此类推）。
3. 使用选择的基数作为模数，依次对字符串中的字符进行哈希操作，计算出一个哈希值。
   哈希值的计算方式通常为：`hash_value = (hash_value * base + char_value) % modulo`
   - `hash_value` 是当前字符串的哈希值，初始化为 0。
   - `base` 是所选的基数。
   - `char_value` 是当前字符的整数值（例如，字符 'a' 对应的整数值）。
   - `modulo` 是一个用来防止哈希值溢出的模数，通常选取一个较大的质数。
4. 重复步骤 3，直到对字符串中的所有字符都进行了哈希操作，最终得到的 `hash_value` 即为字符串的哈希值。
**用途：**
字符串哈希的主要用途包括：
1. 计算字符串的哈希值后，可以将字符串与其哈希值相关联，以便快速比较字符串是否相等。如果两个字符串的哈希值相同，那么它们可能相等。
2. 计算不同字符串的数量：通过将每个字符串的哈希值存储在一个哈希表中，可以快速查找并统计不同字符串的数量。
3. 字符串匹配和模式匹配：哈希值可用于快速比较较长字符串的部分内容，以判断是否匹配。这在一些搜索和匹配算法中非常有用。
4. 数据压缩和数据索引：字符串哈希值可以用于压缩和索引数据，提高数据的检索速度。
需要注意的是，字符串哈希虽然在很多问题中有用，但它也存在一些局限性。例如，不同字符串可能有相同的哈希值，这就是哈希碰撞。为了减小哈希碰撞的概率，通常会选择一个较大的质数作为模数，并谨慎选择哈希函数的基数。


```go
#include <iostream>
#include <vector>

// 自定义哈希函数，用于计算字符串的哈希值
int customHash(const std::string& str) {
    int prime = 31; // 选择一个较大的质数
    int hashValue = 0;

    for (char c : str) {
        hashValue = (hashValue * prime + c) % 1000000007; // 防止哈希值溢出
    }

    return hashValue;
}

int main() {
    int N;
    std::cin >> N; // 读取字符串的个数

    std::vector<std::string> strings; // 用于存储输入的字符串
    std::vector<int> hashValues; // 用于存储字符串的哈希值
    int uniqueCount = 0; // 用于记录不同字符串的数量

    for (int i = 0; i < N; ++i) {
        std::string str;
        std::cin >> str; // 读取每个字符串

        int hashValue = customHash(str); // 计算字符串的哈希值
        bool isUnique = true;

        for (int j = 0; j < i; ++j) {
            // 检查是否已存在相同哈希值的字符串
            if (hashValues[j] == hashValue) {
                isUnique = false;
                break;
            }
        }

        if (isUnique) {
            strings.push_back(str); // 如果是新字符串，存储它
            hashValues.push_back(hashValue); // 存储哈希值
            uniqueCount++; // 唯一字符串数量加一
        }
    }

    std::cout << uniqueCount << std::endl; // 输出不同字符串的数量

    return 0;
}

```

字符串哈希 P3370

P3390




```cpp
#include <iostream>
#include <vector>
#include <cstring>

const int MOD = 1000000007;

// 定义一个矩阵结构
struct Matrix {
    int n;  // 矩阵的维度
    std::vector<std::vector<int>> data;  // 矩阵数据

    Matrix(int _n) : n(_n), data(_n, std::vector<int>(_n, 0)) {}

    // 创建并返回一个单位矩阵
    static Matrix identity(int n) {
        Matrix mat(n);
        for (int i = 0; i < n; ++i) {
            mat.data[i][i] = 1;
        }
        return mat;
    }

    // 矩阵相乘操作
    Matrix operator*(const Matrix& other) const {
        Matrix result(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    // 用模运算防止整数溢出
                    result.data[i][j] = (result.data[i][j] + 1LL * data[i][k] * other.data[k][j] % MOD) % MOD;
                }
            }
        }
        return result;
    }
};

// 矩阵的高次幂计算
Matrix matrixPower(Matrix mat, long long k) {
    int n = mat.n;
    Matrix result = Matrix::identity(n);
    while (k) {
        if (k % 2) {
            result = result * mat;
        }
        mat = mat * mat;
        k /= 2;
    }
    return result;
}

int main() {
    int n, k;
    std::cin >> n >> k;
    Matrix A(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> A.data[i][j];
        }
    }

    Matrix result = matrixPower(A, k);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << result.data[i][j] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

```

矩阵快速幂模板题

主要是一些选举细节代码，不包含其他逻辑，主要是选举部分逻辑



# 初始化时等待就绪
```go
func NewConsensusModule(id int, peerIds []int, server *Server, ready <-chan interface{}) *ConsensusModule {
	cm := new(ConsensusModule)
	cm.id = id
	cm.peerIds = peerIds
	cm.server = server
	cm.state = Follower
	cm.votedFor = -1

	go func() {  // 等待就绪
		// The CM is quiescent until ready is signaled; then, it starts a countdown
		// for leader election.
		<-ready
		cm.mu.Lock()
		cm.electionResetEvent = time.Now()  //重置选举时间
		cm.mu.Unlock()
		cm.runElectionTimer()
	}()

	return cm
}
```
# 开始决定是否投票

```go
// RequestVote RPC.
func (cm *ConsensusModule) RequestVote(args RequestVoteArgs, reply *RequestVoteReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	cm.dlog("RequestVote: %+v [currentTerm=%d, votedFor=%d]", args, cm.currentTerm, cm.votedFor)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in RequestVote")
		cm.becomeFollower(args.Term)
	}

	if cm.currentTerm == args.Term &&
		(cm.votedFor == -1 || cm.votedFor == args.CandidateId) {
		reply.VoteGranted = true
		cm.votedFor = args.CandidateId
		cm.electionResetEvent = time.Now()
	} else {
		reply.VoteGranted = false
	}
	reply.Term = cm.currentTerm
	cm.dlog("... RequestVote reply: %+v", reply)
	return nil
}
```
# 同步日志

```go
func (cm *ConsensusModule) AppendEntries(args AppendEntriesArgs, reply *AppendEntriesReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	cm.dlog("AppendEntries: %+v", args)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in AppendEntries")
		cm.becomeFollower(args.Term)
	}

	reply.Success = false
	if args.Term == cm.currentTerm {
		if cm.state != Follower {
			cm.becomeFollower(args.Term)
		}
		cm.electionResetEvent = time.Now()  //相当于是心跳一次
		reply.Success = true
	}

	reply.Term = cm.currentTerm
	cm.dlog("AppendEntries reply: %+v", *reply)
	return nil
}
```
# 生成选举超时时间

```go
// electionTimeout generates a pseudo-random election timeout duration.
func (cm *ConsensusModule) electionTimeout() time.Duration {
	// If RAFT_FORCE_MORE_REELECTION is set, stress-test by deliberately
	// generating a hard-coded number very often. This will create collisions
	// between different servers and force more re-elections.
	if len(os.Getenv("RAFT_FORCE_MORE_REELECTION")) > 0 && rand.Intn(3) == 0 {
		return time.Duration(150) * time.Millisecond
	} else {
		return time.Duration(150+rand.Intn(150)) * time.Millisecond
	}
}
```
# 选举触发
不断的判断领导是否存活
```go
// runElectionTimer 实现了一个选举计时器。当我们希望启动一个计时器以开始新一轮选举时，
// 应该调用这个方法。这个方法是阻塞的，应该在一个单独的 goroutine 中运行。
// 它为单次（one-shot）的选举计时器设计，因为它会在以下情况下退出：
// - 当 CM 的状态从 Follower/Candidate 改变时
// - 当当前任期（term）改变时
func (cm *ConsensusModule) runElectionTimer() {
	timeoutDuration := cm.electionTimeout() // 获取选举超时时间间隔
	cm.mu.Lock()
	termStarted := cm.currentTerm // 记录选举计时器启动时的当前任期
	cm.mu.Unlock()
	cm.dlog("election timer started (%v), term=%d", timeoutDuration, termStarted)

// 以下是一个循环，它会一直运行，直到发生以下情况之一：
// - 我们发现选举计时器不再需要，或
// - 选举计时器超时，该 CM 成为 Candidate
// 在 Follower 中，这通常在 CM 的生命周期中一直在后台运行。

	ticker := time.NewTicker(10 * time.Millisecond)
	defer ticker.Stop()
	for {
		<-ticker.C

		cm.mu.Lock()
		// 如果 CM 的状态变成 Candidate 或 Follower，则退出选举计时器
		if cm.state != Candidate && cm.state != Follower {
			cm.dlog("在选举计时器中，状态=%s，退出", cm.state)
			cm.mu.Unlock()
			return
		}

		// 如果当前任期（term）改变，则退出选举计时器
		if termStarted != cm.currentTerm {
			cm.dlog("在选举计时器中，任期从 %d 变为 %d，退出", termStarted, cm.currentTerm)
			cm.mu.Unlock()
			return
		}

		// 如果经过了选举超时时间间隔，而且我们还没有收到领袖的消息或者没有投票给其他 Candidate，
		// 则开始一轮新的选举。
		if elapsed := time.Since(cm.electionResetEvent); elapsed >= timeoutDuration {
			cm.startElection()
			cm.mu.Unlock()
			return
		}
		cm.mu.Unlock()
	}
}

```

# 开始选举

```go
// startElection starts a new election with this CM as a candidate.
// Expects cm.mu to be locked.
func (cm *ConsensusModule) startElection() {
	cm.state = Candidate
	cm.currentTerm += 1
	savedCurrentTerm := cm.currentTerm
	cm.electionResetEvent = time.Now()
	cm.votedFor = cm.id
	cm.dlog("becomes Candidate (currentTerm=%d); log=%v", savedCurrentTerm, cm.log)

	votesReceived := 1

	// Send RequestVote RPCs to all other servers concurrently.
	for _, peerId := range cm.peerIds {
		go func(peerId int) {
			args := RequestVoteArgs{
				Term:        savedCurrentTerm,
				CandidateId: cm.id,
			}
			var reply RequestVoteReply

			cm.dlog("sending RequestVote to %d: %+v", peerId, args)
			if err := cm.server.Call(peerId, "ConsensusModule.RequestVote", args, &reply); err == nil {
				cm.mu.Lock()
				defer cm.mu.Unlock()
				cm.dlog("received RequestVoteReply %+v", reply)

				if cm.state != Candidate {
					cm.dlog("while waiting for reply, state = %v", cm.state)
					return
				}

				if reply.Term > savedCurrentTerm {
					cm.dlog("term out of date in RequestVoteReply")
					cm.becomeFollower(reply.Term)
					return
				} else if reply.Term == savedCurrentTerm {
					if reply.VoteGranted {
						votesReceived += 1
						if votesReceived*2 > len(cm.peerIds)+1 {
							// Won the election!
							cm.dlog("wins election with %d votes", votesReceived)
							cm.startLeader()
							return
						}
					}
				}
			}
		}(peerId)
	}

	// Run another election timer, in case this election is not successful.
	go cm.runElectionTimer()
}

```
# 成为Fllower

```go
// becomeFollower makes cm a follower and resets its state.
// Expects cm.mu to be locked.
func (cm *ConsensusModule) becomeFollower(term int) {
	cm.dlog("becomes Follower with term=%d; log=%v", term, cm.log)
	cm.state = Follower
	cm.currentTerm = term
	cm.votedFor = -1
	cm.electionResetEvent = time.Now()

	go cm.runElectionTimer()
}
```
# Leader

```go
// startLeader switches cm into a leader state and begins process of heartbeats.
// Expects cm.mu to be locked.
func (cm *ConsensusModule) startLeader() {
	cm.state = Leader
	cm.dlog("becomes Leader; term=%d, log=%v", cm.currentTerm, cm.log)

	go func() {
		ticker := time.NewTicker(50 * time.Millisecond)
		defer ticker.Stop()

		// Send periodic heartbeats, as long as still leader.
		for {
			cm.leaderSendHeartbeats()
			<-ticker.C

			cm.mu.Lock()
			if cm.state != Leader {
				cm.mu.Unlock()
				return
			}
			cm.mu.Unlock()
		}
	}()
}
```

# 发送心跳

```go
// leaderSendHeartbeats sends a round of heartbeats to all peers, collects their
// replies and adjusts cm's state.
func (cm *ConsensusModule) leaderSendHeartbeats() {
	cm.mu.Lock()
	if cm.state != Leader {
		cm.mu.Unlock()
		return
	}
	savedCurrentTerm := cm.currentTerm
	cm.mu.Unlock()

	for _, peerId := range cm.peerIds {
		args := AppendEntriesArgs{
			Term:     savedCurrentTerm,
			LeaderId: cm.id,
		}
		go func(peerId int) {
			cm.dlog("sending AppendEntries to %v: ni=%d, args=%+v", peerId, 0, args)
			var reply AppendEntriesReply
			if err := cm.server.Call(peerId, "ConsensusModule.AppendEntries", args, &reply); err == nil {
				cm.mu.Lock()
				defer cm.mu.Unlock()
				if reply.Term > savedCurrentTerm {
					cm.dlog("term out of date in heartbeat reply")
					cm.becomeFollower(reply.Term)
					return
				}
			}
		}(peerId)
	}
}
```

raft一些选举细节

```go
// CommitEntry 是 Raft 用来向 commit 通道报告的数据。每个 commit 条目通知客户端一致性已经在一个命令上达成，并且它可以应用于客户端的状态机。
type CommitEntry struct {
	// Command 是正在提交的客户端命令。
	Command interface{}

	// Index 是客户端命令被提交的日志索引。
	Index int

	// Term 是客户端命令被提交的 Raft 任期。
	Term int
}

// CMState 表示 Raft 一致性模块的状态。
type CMState int

const (
	Follower CMState = iota    // 跟随者状态
	Candidate                  // 候选人状态
	Leader                     // 领导者状态
	Dead                       // 无效状态
)

func (s CMState) String() string {
	switch s {
	case Follower:
		return "跟随者"
	case Candidate:
		return "候选人"
	case Leader:
		return "领导者"
	case Dead:
		return "无效状态"
	default:
		panic("不可达的状态")
	}
}

// LogEntry 表示 Raft 日志条目。
type LogEntry struct {
	Command interface{} // 日志条目中的命令
	Term    int         // 日志条目所属的 Raft 任期
}

// ConsensusModule (CM) 实现 Raft 一致性的单个节点。
type ConsensusModule struct {
	// mu 保护对 CM 的并发访问。
	mu sync.Mutex

	// id 是此 CM 的服务器 ID。
	id int

	// peerIds 列出了集群中同伴的 ID。
	peerIds []int

	// server 是包含此 CM 的服务器。它用于向同伴发出 RPC 调用。
	server *Server

	// storage 用于持久化状态。
	storage Storage

	// commitChan 是此 CM 将报告提交的日志条目的通道。在构建过程中由客户端传递。
	commitChan chan<- CommitEntry

	// newCommitReadyChan 是内部通知通道，用于通知提交新条目的 goroutines 可能会发送到 commitChan。
	newCommitReadyChan chan struct{}

	// triggerAEChan 是内部通知通道，用于在发生重要更改时触发向跟随者发送新 AEs。
	triggerAEChan chan struct{}

	// 持久化在所有服务器上的 Raft 状态
	currentTerm int
	votedFor    int
	log         []LogEntry

	// 所有服务器上的易失性 Raft 状态
	commitIndex        int
	lastApplied        int
	state              CMState
	electionResetEvent time.Time

	// 领导者的 Raft 状态
	nextIndex  map[int]int
	matchIndex map[int]int
}

// RequestVoteArgs 表示 RequestVote RPC 的参数。
type RequestVoteArgs struct {
	Term         int // 请求方的当前任期
	CandidateId  int // 请求方的候选人 ID
	LastLogIndex int // 请求方的最后日志索引
	LastLogTerm  int // 请求方的最后日志的任期
}

// RequestVoteReply 表示 RequestVote RPC 的回复。
type RequestVoteReply struct {
	Term        int  // 接收方的当前任期
	VoteGranted bool // 是否授予投票
}

// AppendEntriesArgs 表示 AppendEntries RPC 的参数。
type AppendEntriesArgs struct {
	Term     int         // 领导者的当前任期
	LeaderId int         // 领导者的 ID
	PrevLogIndex int     // 先前日志条目的索引
	PrevLogTerm  int     // 先前日志条目的任期
	Entries      []LogEntry // 要附加到日志的条目
	LeaderCommit int     // 领导者的提交索引
}

// AppendEntriesReply 表示 AppendEntries RPC 的回复。
type AppendEntriesReply struct {
	Term    int  // 接收方的当前任期
	Success bool // 是否成功
	// 更快的冲突解决优化（在文档第 5.3 节末尾有描述）
	ConflictIndex int // 冲突索引
	ConflictTerm  int // 冲突任期
}

```

raft主要几个结构体

一个实现了排序接口的切片，一个往文件写数据的函数，一个生成随机时间的函数，一个断言

utils.go
```go
package raft

import (
	"fmt"
	"io"
	"math/rand"
	"os"
	"time"
)



// uint64Slice implements sort interface
type uint64Slice []uint64

func (p uint64Slice) Len() int           { return len(p) }
func (p uint64Slice) Less(i, j int) bool { return p[i] < p[j] }
func (p uint64Slice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

// WriteFile writes data to a file named by filename.
// If the file does not exist, WriteFile creates it with permissions perm;
// otherwise WriteFile truncates it before writing.
// This is copied from ioutil.WriteFile with the addition of a Sync call to
// ensure the data reaches the disk.
func writeFileSynced(filename string, data []byte, perm os.FileMode) error {
	f, err := os.OpenFile(filename, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, perm)
	if err != nil {
		return err
	}
	defer f.Close() // Idempotent

	n, err := f.Write(data)
	if err == nil && n < len(data) {
		return io.ErrShortWrite
	} else if err != nil {
		return err
	}

	if err = f.Sync(); err != nil {
		return err
	}

	return f.Close()
}

// Waits for a random time between two durations and sends the current time on
// the returned channel.
func afterBetween(min time.Duration, max time.Duration) <-chan time.Time {
	rand := rand.New(rand.NewSource(time.Now().UnixNano()))
	d, delta := min, (max - min)
	if delta > 0 {
		d += time.Duration(rand.Int63n(int64(delta)))
	}
	return time.After(d)
}

// TODO(xiangli): Remove assertions when we reach version 1.0

// _assert will panic with a given formatted message if the given condition is false.
func _assert(condition bool, msg string, v ...interface{}) {
	if !condition {
		panic(fmt.Sprintf("assertion failed: "+msg, v...))
	}
}
```