目录
前言
前面使用ldb看了看不同的类型，这篇再使用lldb就来看看HashMap
正文
use std::collections::HashMap;
fn main() {
let mut map = HashMap::new();
// 插入键值对
map.insert("go", "tt");
map.insert("66", "123");
map.insert("ok", "no");
println!("最终的 HashMap: {:?}", map);
}这段简单地的代码，笔者在println哪里打个断点，然后用lldb查看
首先
p map
效果和expr 的等效的
(lldb) p map
(std::collections::hash::map::HashMap<ref$<str$>,ref$<str$>,std::hash::random::RandomState>) map = {
base = {
hash_builder = (k0 = 4722932796647620636, k1 = 13347288390664849048)
table = {
table = {
bucket_mask = 3
ctrl = {
pointer = 0x000001bc42010e00
}
growth_left = 0
items = 3
}
alloc = {}
marker = {}
}
}
}这个就看出HashMap在Rust的结构吧，笔者也不知道用什么词表示，就用结构这个词表示。
这里最关键的东西，显然易见是pointer，里面是一个地址。
结合HashMap有关的知识
【数据结构】哈希表-CSDN博客
https://blog.csdn.net/jmlangel_/article/details/147423680
7. HashMap的底层数据结构 - 知乎https://zhuanlan.zhihu.com/p/636054806
关注
bucket_mask = 3
ctrl = {
pointer = 0x000001bc42010e00
}
growth_left = 0
items = 3
这几个的意思
bucket_mask = 3：哈希表有 3+1 个桶。
ctrl.pointer = 0x000001bc42010e00：控制字节数组的起始地址。
growth_left = 0：哈希表已经满了。
items = 3：哈希表中有 3 个键值对
这里面只有一个地址，就从这里开始
读取桶的状态
memory read -c 4 0x000001bc42010e00
memory read 是lldb命令，-c 4 表示读取4个字节的内容
为什么是4 ，因为有4个桶。
关于桶的状态如下
| 状态 | 描述 | 控制字节值 | 备注 |
|---|---|---|---|
| 占用 (Occupied) | 桶中存储了有效的键值对 | < 0x80 (高位为 0) |
通常为哈希值的高 7 位 (hash >> 57)，用于快速比较哈希 |
| 空 (Empty) | 桶未被使用，当前没有键值对 | 0x80 (二进制 10000000) |
表示桶从未存储数据 |
| 已删除 (Tombstone) | 桶曾存储键值对，但数据已被删除 | 0xff (二进制 11111111) |
用于标记移除的条目，避免破坏哈希表的探查链 (probe chain) |
运行结果如下
(lldb) memory read -c 4 0x000001bc42010e00
0x1bc42010e00: 70 ff 06 7f 70 是小于80，因此是占有，索引为1 。
ff 表示曾经占有 ，
06 是小于80，因此是占有 ，索引为3。
7f 是小于80，因此是占有，索引为4 。
获取键值对
怎么获取键值对，这确实是一个的问题？
笔者添加一个循环，打上断点
for (k,v) in &map{
println!("{:?},{:?}",k,v);
}看看k，v
此时，地址发生变换，重新执行上面的命令
(lldb) memory read -c 4 0x000002a0336c0e00
0x2a0336c0e00: ff 7a 75 4c发现了变换，还是三个，但是索引是2，3，4了
ctrl指针的地址是0x2a0336c0e00，笔者复制出来，没有前面的0，不影响
k的地址是 0x2a0336c0dc0
二者之差，等于0x40，变成十进制就是64
有这样一个公式
桶的起始地址 = 桶数组的起始地址 + (桶索引 × 桶的大小)现在有两个地址，有索引2，笔者的电脑是64位的
&str有两个部分组成，一个指向数据的地址，占8个字节，还有一个是长度u64，也是8个字节，因此，一个&str，占16个字节
同时考虑到键值对都是&str，因此桶的大小为32字节
实际上可以使用std::mem
即
use std::mem;
println!("(&str, &str) {}", mem::size_of::<(&str, &str)>());结果如下
(&str, &str) 32
没问题
同时考虑到索引为2 ，因此2乘以32等于64，两个地址之差正是64
没问题。
经过多次尝试。可以发现
通过ctrl的pointer的地址，减去 (桶索引 × 桶的大小)，就可以算出一个地址。这个地址就是键值对的指针地址。
键值对的指针地址
再次运行命令，获取索引
现在ctrl pointer的地址变成了0x00000277412c0e00
(lldb) memory read -c 4 0x00000277412c0e00
0x277412c0e00: 17 ff 5d 04索引为1，3，4
因此0x00000277412c0e00-32=0x00000277412c0de0
同时考虑到笔者是64位的电脑，读取一个指针需要8个字节
因此
(lldb) memory read -c 8 0x00000277412c0de0
0x277412c0de0: 9c 1b e2 61 f6 7f 00 00
这就是指针的地址
笔者的操作系统储存数据的方式是小端序，因此
指针地址为
0x00007ff661e21b9c
此时，读取数据
(lldb) memory read -c 5 0x00007ff661e21b9c
0x7ff661e21b9c: 36 36 31 32 33 66123
为什么读取5个，这是笔者主动选择的，
看到66123，
结合代码，66是键，123是值，读取到键值对
读取索引4的键值对
0x00000277412c0e00 -4*32=0x00000277412c0d80
指针为
(lldb) memory read -c 8 0x00000277412c0d80
0x277412c0d80: a1 1b e2 61 f6 7f 00 00 地址为0x00007ff661e21ba1
键值对
(lldb) memory read -c 4 0x00007ff661e21ba1
0x7ff661e21ba1: 6f 6b 6e 6f okno没问题
看看是否可以修改
(lldb) memory region 0x00007ff661e21ba1
[0x00007ff661e00000-0x00007ff661e2c000) r--发现不可以修改。没有写的权限
多添加几个键值对
map.insert("go", "tt");
map.insert("66", "123");
map.insert("ok", "no");
map.insert("hello1","world1");
map.insert("hello2","world2");
map.insert("hello3","world3");
map.insert("hello4","world4");
map.insert("hello5","world5");p map的结果如下
(lldb) p map
(std::collections::hash::map::HashMap<ref$<str$>,ref$<str$>,std::hash::random::RandomState>) map = {
base = {
hash_builder = (k0 = 12591853735628107626, k1 = 11397258469864990867)
table = {
table = {
bucket_mask = 15
ctrl = {
pointer = 0x000002ea70e2c090
}
growth_left = 6
items = 8
}
alloc = {}
marker = {}
}
}
}可以发现bucket_mask 变成了15，就有16个桶
因此，第一个内存的读取，桶的状态
(lldb) memory read -c 16 0x000002ea70e2c090
0x2ea70e2c090: 4a ff ff 0a 48 15 ff 60 ff 3c 2a ff ff 4d ff ff
索引分别是1、4、5、6、8、10、11、14
桶的大小依然是32，不妨读取索引8
地址为0x000002ea70e2c090 - 0x100 = 0x000002ea70e2bf90
指针地址为
(lldb) memory read -c 8 0x000002ea70e2bf90
0x2ea70e2bf90: c9 1b 48 e9 f6 7f 00 00
即 0x00007ff6e9481bc9
(lldb) memory read -c 12 0x00007ff6e9481bc9
0x7ff6e9481bc9: 68 65 6c 6c 6f 34 77 6f 72 6c 64 34 hello4world4
看来是hello4这个键。其他同理
使用i32作为键，&str作为值
看看桶的大小
println!("(i32,&str) {}", mem::size_of::<(i32, &str)>());(i32,&str) 24
i32是4字节，Rust 默认会按 8字节对齐，笔者是64位
因此8+16=24
插入键值对
map.insert(1, "tt");就一个
关键输出
ctrl = {
pointer = 0x0000013c22361450
}获取桶的状态
(lldb) memory read -c 4 0x0000013c22361450
0x13c22361450: ff ff ff 39 索引为4
因此，key地址为
0x0000013c22361450 - 4*24
0x0000013c22361450- 0x60 = 0x000001d9c0da13f0
因为key是一个i32
此时这个地址——0x000001d9c0da13f0，就是key的地址
即
(lldb) p *(0x000001d9c0da13f0 as *mut u8)
(u8) * = 1value的指针地址就是0x000001d9c0da13f8，不必细说
笔者重新运行。结果如下
(lldb) memory read -c 4 0x000001a895741880
0x1a895741880: ff ff ff 74
(lldb) p *(0x000001a895741820 as *mut i32)
(i32) * = 1
(lldb) memory read -c 8 0x000001a895741828
0x1a895741828: b8 1b 80 a2 f7 7f 00 00
(lldb) memory read -c 2 0x00007ff7a2801bb8
0x7ff7a2801bb8: 74 74 tt没问题
使用i32作为键，String作为值
首先，看看桶的大小
let size= mem::size_of::<(i32, String)>();
println!("size of (i32, String): {}", size);size of (i32, String): 32
可以得到是32
插入数据
// 插入键值对
map.insert(1, "tt".to_string());先打印看看
for (key, value) in &map {
println!("key: {}, value: {}", key, value);
}
结果如下
key是*mut i32
value 是*mut alloc::string::String
key与value差了0x8
直接开始
(lldb) p map
(std::collections::hash::map::HashMap<i32,alloc::string::String,std::hash::random::RandomState>) map = {
base = {
hash_builder = (k0 = 14409132009700107725, k1 = 6608230683712741401)
table = {
table = {
bucket_mask = 3
ctrl = {
pointer = 0x000001f8d3781470
}
growth_left = 2
items = 1
}
alloc = {}
marker = {}
}
}
}ctrl的地址0x000001f8d3781470
看看桶的状态
(lldb) memory read -c 4 0x000001f8d3781470
0x1f8d3781470: 5d ff ff ff 索引为1
因此 key 的地址0x000001f8d3781470-32=0x000001f8d3781450
即
(lldb) p *(0x000001f8d3781450 as *mut i32)
(i32) * = 1没问题
key是i32，占8个字节，因此value的地址0x000001f8d3781458
同时考虑到value是一个字符串，在前面输出中是*mut alloc::string::String，
因此，笔者尝试
(lldb) p (0x000001f8d3781458 as *mut alloc::string::String)
(*mut alloc::string::String) = 0x000001f8d3781458没想到居然成功了
(lldb) p *(0x000001f8d3781458 as *mut alloc::string::String)
(alloc::string::String) * = {
vec = {
buf = {
inner = {
ptr = {
pointer = {
pointer = 0x000001f8d37861f0
}
_marker = {}
}
cap = (__0 = 2)
alloc = {}
}
_marker = {}
}
len = 2
}
}那后面的事情就不必细说了。都有地址了。
即
(lldb) memory read -c 2 0x000001f8d37861f0
0x1f8d37861f0: 74 74 tt 没问题
笔者感到很奇怪，为什么&str不行
如果改成&str，输出是这样的
但是
(lldb) p *(0x0000015a3ef96190 as *mut &str)
error: could not find type "str"笔者不能理解。
但是对于i32为键， &str为值，获取到了key的地址
map.insert(1,"ggggg");比如
(lldb) p *(0x000001f296071820 as *mut i32)
(i32) * = 1这个0x000001f296071820 就看key的地址
0x000001f296071820+0x8=0x000001f296071828
0x000001f296071828 就是value的地址
而value是&str，包括两个部分，一个数据指针，一个是长度
总共是16个字节，因此，如下
(lldb) memory read -c 16 0x000001f296071828
0x1f296071828: b8 1b d2 34 f6 7f 00 00 05 00 00 00 00 00 00 00前8个字节b8 1b d2 34 f6 7f 00 00 ，数据指针，05 就是长度
数据
(lldb) memory read -c 5 0x00007ff634d21bb8
0x7ff634d21bb8: 67 67 67 67 67 ggggg长度，value的地址+8个字节，即
0x000001f296071828 +0x8=0x000001f296071830
(lldb) memory read -c 1 0x000001f296071830
0x1f296071830: 05
(lldb) p *(0x000001f296071830 as *mut u8)
(u8) * = 5