跳转至

14. 比特币和哈希

阅读信息

约 1085 个字  4 分钟  本页总访问量：加载中... 次

Class Fourteen

比特币

发行:比特币总量一定,每十分钟发行,每四年每十分钟发行量减半 流通

  • 怎么证明是自己的? 中心式数据库,每个人有账号和密码
  • 怎么防止"双花"? 每个账号记录余额

比特币不受统一控制,不能建立中心式数据库.采用分布式账本. 解决分布式账本之间可能不同的问题:每隔一定时间选择一个人记录,将账本复制后分发,后续可补充

新交易创建 -> 交易通过 P2P 网络传播 -> 交易验证 -> 验证结果通过 P2P 网络传播 -> 交易写入账本

记账有好处,竞争计算速度.给定哈希函数生成值,计算输入值.(容易形成共识) 矿机:专门计算输入值的计算机 矿池:多台矿机 挖矿:猜输入值

怎么控制输出值 y? y 有 128 位.如果 128 位全部随机生成,最大有 2^128 种,计算时间很长. 根据最近挖矿的计算机数量,限制 y 中 0 的个数,保证 10 分钟左右能挖到.

智能合约:普通程序,用来执行合同规定的某些条款. 问题:程序在信息空间,怎么判断物理空间中是否完成业务? 解决:找中间媒介,证明业务完成. 防止中间媒介造假:将数据传入区块链

哈希

哈希函数:以空间换时间,哈希值代表位置(区块链中代表指纹) 应用: 字典,搜索引擎({键:值}) 搜索引擎:用爬虫爬取所有网页信息,将页面看成节点,构成巨大的图 -> 可能由不同路径到达同一个网页,需要对网页做标记(URL 地址),存储到 URL 集合 -> 直接比较 URL 则时间长,利用哈希函数,计算 URL 的哈希值

倒排索引:按关键词存储. 查询时找不同关键词的交集

哈希表:计算出 f(x)放到一行 identifier density : n/T (要存储的数据总数 / 通过哈希函数算出的值的所有可能值的总数) loading density : n/(sb) (要存储的数据总数 / (slots * buckets))

collision : 不同输入值有相同输出 overflow : 要存储的数据总数大于空间总数(同一输出值对应的输入值数量 > slots)

哈希函数的设计

要求:: 容易计算,输出均匀

整数:

  1. 求余法: x -> x%p,一般取 p 为素数
  2. 折叠法: 将长整数映射为两位数,则两位一段再相加,中间可以颠倒等
  3. 平方取中: 平方后取中间的一段,使结果能被多位影响
  4. 分析法

字符串: 字符串怎么变成数据?

  1. 相加求余数. 防止输出值集中在较小值,可以str[0]+str[1]*27+str[2]*27*27....(用 32 代替 27 可加快计算,从最高位开始乘一次,每次加新的值再移位)

冲突解决方法

  1. seperate chaining 链地址法
C
1
2
3
4
struct HashTbl {
  int tableSize;
  List *theList;
};

theList中存储带头链表

  1. open address 开放地址法 h(k) + f(i),冲突时i++或+-i,f(i)为线性时称为线性探测 删除时可能判断错误,故删除时要做标记 average search time 平均成功查找次数: 所有 search time 相加求平均 平均不成功查找次数: 按入口分类

线性探测冲突多,换成二次探测,依次调整为f(i)=i^2, f(i)=i^3..., 超出范围时求模返回 二次探测可能发生二次聚集 缺点:不一定能探测到空位

  1. 公共区域 冲突时开辟统一的新区域，存放冲突值。每次访问时先看原来的位置，空表示要访问的数不在；有数再看新区域，访问要访问的值。

补充

Loading Density 是什么

1. 定义 Loading Density（也称为 Load Factor，装载因子）表示哈希表中已存储元素数量与哈希表总容量的比值：
[ \text{Loading Density} = \frac{\text{已插入的元素数量}}{\text{哈希表的总槽位数（Size）}} ]

2. 作用

  • 衡量空间利用率：值越高，说明哈希表越“满”。
  • 影响性能：
  • 装载密度越高，发生哈希冲突的概率越大，查找/插入操作可能变慢。
  • 通常需要设定一个阈值（如 0.7），超过时触发扩容（Rehashing）。

3. 与冲突的关系

  • 低装载密度（<0.5）：冲突概率低，但空间浪费较多。
  • 高装载密度（>0.7）：冲突概率显著增加，线性探测等方法的性能下降。

常见策略：

  • 当装载密度超过阈值（如 0.75），哈希表会扩容（通常加倍大小），并重新哈希所有元素。