Scala实现功能性迷你区块链：数据结构选型与区块关联疑问

嘿，这个问题问到点子上了——区块链的分叉处理和区块引用确实是实现迷你链时最容易卡壳的地方，尤其是用Scala这种函数式语言，得兼顾不可变性和易用性。我来结合函数式风格给你拆解这两个疑问：

1. 处理分叉的数据结构选择：别纠结线性结构，用「哈希映射+头部集合」组合 #

你说得对，普通的LinkedList/Stack完全搞不定分叉，因为它们是严格线性的，没法同时追踪多个并行的链分支。我推荐用两个不可变数据结构的组合，这也是大多数区块链实现的核心思路：

• Map[Hash, Block]：把每个区块的哈希值作为键，区块本身作为值，这样可以O(1)时间快速查找任意区块，不管它在哪个分支里。
• Set[Hash]：存储所有「顶层区块」（也就是没有子区块的头部）的哈希值。当分叉产生时，只需要把新的头部哈希加入集合，同时移除被替代的父区块哈希就行。

用Scala代码来定义的话，大概是这样：

// 先定义基础类型，Hash可以用String或者更安全的类型（比如SHA-256的字节数组）
type Hash = String

// 区块的不可变类：prevHash用Option处理创世块（没有前序区块）
case class Block(
  hash: Hash,
  prevHash: Option[Hash],
  data: String,
  height: Int // 区块高度，创世块为0，每往后加1
)

// 整个区块链的核心结构，全是不可变类型
case class Blockchain(
  blocks: Map[Hash, Block], // 存储所有区块的哈希映射
  heads: Set[Hash]          // 所有分支的顶层区块哈希
)

这个结构的优势很明显：

• 处理分叉：比如当某个区块A同时有两个子区块B和C时，只需要把B和C的哈希加入heads，并把A的哈希从heads中移除（因为A不再是顶层了）。
• 遍历分支：从heads里的任意哈希出发，通过prevHash递归/迭代查找前序区块，就能完整遍历整个分支，直到碰到prevHash = None的创世块。

2. 通过哈希找到前序区块：靠哈希映射直接查找 #

每个区块里的prevHash就是钥匙——你已经在区块里存了前序区块的哈希，现在只需要用这个哈希去blocks映射里查对应的区块就行。用Scala的函数式风格实现的话，可以写个纯函数来获取前序区块：

// 给定一个区块，返回它的前序区块（如果存在）
def getPreviousBlock(block: Block)(bc: Blockchain): Option[Block] = {
  block.prevHash.flatMap(bc.blocks.get)
}

如果要遍历整个分支（比如从某个头部区块回溯到创世块），可以写个递归函数：

// 从指定头部哈希出发，返回完整的链分支（从头部到创世块）
def getFullBranch(headHash: Hash)(bc: Blockchain): List[Block] = {
  bc.blocks.get(headHash) match {
    case None => Nil // 如果哈希不存在，返回空列表
    case Some(block) =>
      block :: getFullBranch(block.prevHash.getOrElse(""))(bc)
      // 注意：创世块的prevHash是None，getOrElse("")会返回空字符串，此时bc.blocks.get会返回None，递归终止
  }
}

这里要注意创世块的处理：创世块的prevHash必须是None，这样递归到它的时候就会停止，不会无限循环。

额外的函数式小技巧 #

因为Scala默认的集合都是不可变的，所以每次修改区块链（比如添加新区块）时，都是生成一个新的Blockchain实例，完全符合函数式的纯函数要求。比如添加新区块的函数可以这么写：

// 添加新区块到区块链
def addBlock(newBlock: Block)(bc: Blockchain): Blockchain = {
  // 先检查新区块的前序区块是否存在
  bc.blocks.get(newBlock.prevHash.getOrElse("")) match {
    case None => bc // 前序区块不存在，不添加
    case Some(_) =>
      // 更新blocks映射，加入新区块
      val updatedBlocks = bc.blocks + (newBlock.hash -> newBlock)
      // 更新heads：移除新区块的父区块哈希（如果它是之前的头部），加入新区块的哈希
      val updatedHeads = bc.heads - newBlock.prevHash.get + newBlock.hash
      Blockchain(updatedBlocks, updatedHeads)
  }
}

如果要实现「最长链优先」的规则，只需要从heads里找出高度最大的区块作为主链头部：

// 获取主链的头部区块（高度最高的那个）
def getMainChainHead(bc: Blockchain): Option[Block] = {
  bc.heads.toList
    .flatMap(bc.blocks.get) // 把哈希转成区块
    .sortBy(-_.height)      // 按高度降序排序
    .headOption             // 取第一个（最高的）
}

内容的提问来源于stack exchange，提问作者Aarsh Shah