分享 HashMap 如何组织键值对

early · 2019年03月19日 · 515 次阅读

数据结构之HashMap中简要介绍了HashMap的作用、原理、冲突解决、一致性hash和并发等问题,以PPT的视角大致整合了HashMap的知识结构,蜻蜓点水。

本文尝试在上面文章的基础上,进一步关注偏底层一点的知识: HashMap如何在内存中组织键值对?

接下来通过简单梳理Redis、Ruby(动态语言)、Golang(静态语言)中HashMap的部分实现,来解答上面的问题,如有不对的地方,还请不吝赐教。

初识问题

在刚学习Golang的时候, 会遇到静态语言蛋疼的类型声明:

var hash map[string] int

会发现HashMap的key和value都各自有类型,map的底层抽象需要能适应多类型的场景,在常规意识中,key和value是捆在一起的,而类型声明让这件事情看起来更复杂了。

从Redis的角度来看这稍微简单,Redis的十多个逻辑database实际上每个都是HashMap,不过它的key都是sds,而value通过RedisObject统一抽象,内部通过type来区分是哪种数据结构,类型表面看起来是固定的。

从Ruby的角度来看就更简单了,动态语言的类型会在运行的时候进行解析,使用者根本不用关心。简单的HashMap抽象可以是下面:

class Hash
   attr_accessor :entries # 数组,用来存放键值对
   attr_accessor :size, :mask
end

class Entry # 键值对的核心抽象
  attr_accessor :key, :value, :next 
end

hashMap的核心结构中始终分为两部分:

  • 一个数组(table)
  • Entry 用来打包 key-value等数据

有一个数组,其中存放着Entry,HashMap近似O(1)的时间复杂度就是得益于数组的随机访问特性。而根据解冲突的方案等的不同,Entry的结构有差异有不同的实现。 一般用链表解冲突的方案中,其Entry中都会有一个next指针,而开放寻址的就没有这个指针。

当然实际情况不会这么简单,接下来就看看更为复杂的真正实现。

Ruby的实现

Ruby的hash实现在2.4的时候有一次大改,核心点是引入了开放寻址的解冲突方案,让性能大幅提升。貌似为了向后兼容,两种实现现在都还在源码中,通过C中的union来整合:

//https://github.com/ruby/ruby/blob/v2_6_0/internal.h#L835
struct RHash {
    struct RBasic basic;
    union {
        st_table *st; //新方案
        struct ar_table_struct *ar; /* 旧方案 */
    } as;
    const int iter_lev;
    const VALUE ifnone;
};

新方案在st.c中,来看看新方案的细节。

// https://github.com/ruby/ruby/blob/v2_6_0/include/ruby/st.h#L79
struct st_table {
    /* Cached features of the table -- see st.c for more details.  缓存一些数字,例如大小*/
    unsigned char entry_power, bin_power, size_ind;
    /* How many times the table was rebuilt.  */
    unsigned int rebuilds_num;
    const struct st_hash_type *type; /* hash函数等方法定义*/
    /* Number of entries currently in the table.  */
    st_index_t num_entries;
    /* Array of bins used for access by keys.  */
    st_index_t *bins; /* 核心实现之一 , 通过这个数组用来实现开放寻址*/
    /* Start and bound index of entries in array entries.
       entries_starts and entries_bound are in interval
       [0,allocated_entries].  */
    st_index_t entries_start, entries_bound;
    /* Array of size 2^entry_power.   */
    st_table_entry *entries; /*核心实现之二 存放实际的键值对,将数组下表存放在bins中*/
};

上面的是hashMap的table核心结构,需重点关注的有两个地方:

  • *bins数组,通过key的hash值来实现开放寻址,数组中存放的是下面entries的下标
  • *entries数组,实际存放键值对的地方,按照插入的先后顺序存放
  bins:
 -------
|5      |                  entries array:
|-------|            --------------------------------
|1      |           |      | entry:  |        |      |
|-------|           |      |         |        |      |
| ...   |           | ...  | hash    |  ...   | ...  |
|-------|           |      | key     |        |      |
| empty |           |      | record  |        |      |
|-------|            --------------------------------
| ...   |                   ^                  ^
|-------|                   |_ entries start   |_ entries bound
|deleted|
 -------

如果要存放一个key-value,有两步:

  1. 将key-value追加到entries中,记录其所在的下标
  2. 获取key的hash值,通过开放寻址探测到key应该存放的位置,将第一步中的下标存放到bins中

在通过key查询的时候,是先到bins中找到key-value在entries中的下标,然后通过下标再去entries中找到实际的key-value。

接下来关注本文的重点,key-value是如何抽象的:

struct st_table_entry {
    st_hash_t hash; // key的hash值
    st_data_t key; // key的指针,st_data_t 定义在下面
    st_data_t record; // value的指针
};

#if SIZEOF_LONG == SIZEOF_VOIDP
typedef unsigned long st_data_t; // 重点
#elif SIZEOF_LONG_LONG == SIZEOF_VOIDP
typedef unsigned LONG_LONG st_data_t;
#else
# error ---->> st.c requires sizeof(void*) == sizeof(long) or sizeof(LONG_LONG) to be compiled. <<----
#endif

可以看出st_data_t其实是long,大小就等价于一个void指针,也就是说Ruby在组织key-value时是简单地在entries中存放其各自的指针,将其打包到一个结构体中,而entries里面存放的则是结构体的指针。

Ruby在实现hashMap是根本就没有考虑对象的类型问题,之所以可以这样,是因为Ruby GC几乎将所有对象进行了统一抽象,通过RVALUE结构体来实现:

typedef struct RVALUE {
    union {
        struct {
            unsigned long flags;   /* 0 if not used */
            struct RVALUE *next;
        } free;
        struct RBasic  basic;
        struct RObject object;
        struct RClass  klass;
        struct RFloat  flonum;
        struct RString string;
        struct RArray  array;
        //·····
    } as;
} RVALUE;

Redis 的实现

redis的hashMap在代码中被成为dict,通过链表方案解决冲突问题,所以dictEntry的核心实现中会有next指针。

// https://github.com/antirez/redis/blob/4.0.0/src/dict.h#L47
typedef struct dictEntry { //Entry实现
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; //next指针
} dictEntry;

/* Table的核心实现 */
typedef struct dictht {
    dictEntry **table;  // Entry数组
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type; // hashMap的各种方法,hash函数等
    void *privdata;
    dictht ht[2]; // 有两个table,一新一旧,用来实现增量迁移
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

由上面的代码可以看出,key是通过指针直接存放,指向的其实是sds,全名叫简单动态字符串,其实现也是通过一个字符数组实现,可以弹性扩容,其类型是可以认为就是字符串。

而value会根据对象来区别对待,如果是数字的话直接存储,是对象的话则存放指针。指针对应的是一个redisObject,通过type可以知道具体是哪种对象:

#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4
// https://github.com/antirez/redis/blob/4.0.0/src/server.h#L584
typedef struct redisObject {
    unsigned type:4; // type有上面的5种
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits decreas time). */
    int refcount;
    void *ptr; // 指向实际的对象
} robj;

Golang的实现

go的实现相对复杂:

// https://github.com/golang/go/blob/release-branch.go1.10/src/runtime/hashmap.go#L108
// A header for a Go map.
type hmap struct {
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // table的实现, 指向一个 2^B 个Buckets的数组
    //它也有两个table,和redis一样用来实现增量迁移,将扩容时的消耗分散在多个操作中,避免单次操作延迟过高。
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // 溢出链,会存放冲突的键值对
}

golang的实现让人困惑,它没有用一个特定的struct来抽象table的结构,只是在hmap中保留table的指针,table是一块连续的内存块,大小为2^B个Bucket,一个Bucket的实际大小根据key和value的类型不同而不同。

在上面Redis和Ruby的方案中,每个Entry都只存放一个key-value对,而Golang的一个Bucket 会存放8组key-value,Bucket中的key-value会打包压在一起。当Bucket中空间不够时,会另外申请额外的一个Bucket,Bucket间通过指针连接,额外申请的Bucket也被称作溢出Bucket。

下面是Bucket的核心结构:

// A bucket for a Go map.
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    tophash [bucketCnt]uint8 // 第一部分,有8个元素的数组
        // 第二部分是key-value对,空间可存放8对
        // 第三部分是Bucket指针,指向下一个Bucket,如果有的话

}

struct中只有第一部分的tophash,第二部分和第三部分都是通过指针操作来进行的。在为Bucket分配空间时,会根据map的类型计算出三部分空间的总和一起分配成一块连续的内存空间。

第一部分是一个大小为8的数组,用来存放8个key-value对中key的hash值的高位,数组下标会对齐。由于每个Bucket中有8对key-value,意味着当定位到某个Bucket后还需要遍历Bucket中的key-value才能找到对应的数据,这个遍历操作相对昂贵,而tophash的核心作用就是加速这个遍历过程,遍历Bucket时直接遍历tophash,依次对比hash值的高位,找到相等的后再根据下标去定位key-value,避免直接对比key(数字间对比的性能字符串等好很多)。

第二部分是本文关注的核心点,key和value的类型可能会有多种,在申明map时确定。与上面方案不同的是golang*将key和value分开存放*,在Bucket内部是将8对key依次放在一起,8个value依次放在一起,类似列式储存。 具体原因是,Bucket中key和value是以数组的形态存放的,为了能随机查找,必须要字节对齐,而key和value的类型有可能是不一样的,在字节对齐的时候就会造成内部碎片。而key之间或value之间类型是一样的,对齐不会造成碎片,这样做是用复杂性换效率。

内存布局大致为下图:

第一层bucket数组是在初始化时分配,overflow层在空间不够时单独分配。值得注意的是,在存放key或value时如果其内存占用小于128字节,则数据是直接存放在Bucket中,否则只会在Bucket中保留指针。

参考链接

暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册