前言

这一章,我们学习了查找这种基本操作和堆、散列表这两种非常重要的数据结构。 本笔记主要完成了以下工作:

  • 总结了关于查找的各种知识点
  • 用ruby语言实现了一个简单的堆模块(这里的模块指module,是ruby中MIX_IN思想的主要实现模式,下面会做简短介绍),并进行了简单测试
  • 用C++语言实现了一个简单的哈希表,并进行了简单测试
  • 讨论了ruby中哈希表的实现
  • 讨论了stl中std::find, std::binary_search等函数的实现

查找的基本定义

查找也可以视为搜索,wikipedia对搜索的定义是:

在计算机科学中,搜索算法是解决搜索问题的任何算法,即检索存储在某个数据结构中的信息,或者在问题域的搜索空间中计算的信息。 其实简单来说,查找就是“找东西”。

而我们要找的“东西”,严格来说应该叫做“关键字”,或者更学术一些,叫做“键”。找到“键”之后,如果存在一个“键-值映射”,就可以得到其“值”。

查找算法的分析和设计

查找算法实际上包含三个层次的问题:

  1. 在什么数据结构上查找
  2. 如何查找
  3. 查找的效率如何

顺序查找算法

顺序查找是最朴素的查找,可以用在各种线性表上。在MSVC的stl中,我们有std::find函数实现这个算法:

以下代码来自<algorithm>

template <class _InIt, class _Ty>
_NODISCARD inline _InIt find(_InIt _First, const _InIt _Last, const _Ty& _Val) { // find first matching _Val
    _Adl_verify_range(_First, _Last);
    _Seek_wrapped(_First, _Find_unchecked(_Get_unwrapped(_First), _Get_unwrapped(_Last), _Val));
    return _First;
}

_Adl_verify_range是检查参数范围是否有效,_Seek_wrapped函数简单来说是把后一个参数的值赋给前一个参数:


template <class _Ty>
constexpr void _Seek_wrapped(_Ty*& _It, _Ty* const _UIt) {
    _It = _UIt;
}

实际查找过程在_Find_unchecked函数中:

template <class _InIt, class _Ty>
inline _InIt _Find_unchecked(const _InIt _First, const _InIt _Last, const _Ty& _Val) {
    // find first matching _Val; choose optimization
    // activate optimization for pointers to (const) bytes and integral values
    using _Memchr_opt = bool_constant<
        is_integral_v<_Ty> && _Is_any_of_v<_InIt, char*, signed char*, unsigned char*, //
            const char*, const signed char*, const unsigned char*>>;

    return _Find_unchecked1(_First, _Last, _Val, _Memchr_opt{});
}

而这个函数实际上又调用了_Find_unchecked1函数:

template <class _InIt, class _Ty>
inline _InIt _Find_unchecked1(_InIt _First, const _InIt _Last, const _Ty& _Val, false_type) {
    // find first matching _Val
    for (; _First != _Last; ++_First) {
        if (*_First == _Val) {
            break;
        }
    }

    return _First;
}

谢天谢地,_Find_unchecked1函数就是主要实现了。我们可以看到整个过程非常简单,就是顺序地查找整个表,如果找到了就退出。

由于模板的存在,在c++中,只要定义了迭代器,一个类就可以使用这个函数进行查找。这也正是对我们抽象描述–查找线性表–的抽象实现。

如果假设等概率,这个算法有

\(ASL_{success} = \frac{n + 1}{2}\) \(ASL_{fail} = n + 1\)

二分查找算法与二叉查找树

从上面的分析可以看出,顺序查找查找一次的时间复杂度是$O(n)$的。可不可以有更好的效率呢?

如果假定顺序表是有序的,那么思考这样的结论:

如果待查询的元素大于 $array[floor(n / 2)]$,那么,它一定大于$array[0]$到$array[floor(n / 2) - 1]$的所有元素。

这样一来,下一次的查询就可以不管这些元素,直接查询$array[floor(n/2) + 1]$到$array[n - 1]$这个区间了。

这实际上已经是一个递归算法了。这个算法的实现很简单,但我们还是来研究一下c++ stl中std::binary_search的实现:

template <class _FwdIt, class _Ty>
_NODISCARD inline bool binary_search(
    _FwdIt _First, _FwdIt _Last, const _Ty& _Val) { // test if _Val equivalent to some element, using operator<
    return _STD binary_search(_First, _Last, _Val, less<>());
}

下面这个binary_search是一个重载的函数,它才是真正用来实现的函数:

// FUNCTION TEMPLATE binary_search
template <class _FwdIt, class _Ty, class _Pr>
_NODISCARD inline bool binary_search(
    _FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Pr _Pred) { // test if _Val equivalent to some element, using _Pred
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    _UFirst           = _STD lower_bound(_UFirst, _ULast, _Val, _Pass_fn(_Pred));
    return _UFirst != _ULast && !_Pred(_Val, *_UFirst);
}

这看起来并不是直接递归,而是使用了一个lower_bound函数。这个函数是干什么的呢?显然的,lower_bound的意思是下界,它定义如下:

// FUNCTION TEMPLATE lower_bound
template <class _FwdIt, class _Ty, class _Pr>
_NODISCARD inline _FwdIt lower_bound(_FwdIt _First, const _FwdIt _Last, const _Ty& _Val, _Pr _Pred) {
    // find first element not before _Val, using _Pred
    _Adl_verify_range(_First, _Last);
    auto _UFirst                = _Get_unwrapped(_First);
    _Iter_diff_t<_FwdIt> _Count = _STD distance(_UFirst, _Get_unwrapped(_Last));

    while (0 < _Count) { // divide and conquer, find half that contains answer
        const _Iter_diff_t<_FwdIt> _Count2 = _Count >> 1; // TRANSITION, VSO#433486
        const auto _UMid                   = _STD next(_UFirst, _Count2);
        if (_Pred(*_UMid, _Val)) { // try top half
            _UFirst = _Next_iter(_UMid);
            _Count -= _Count2 + 1;
        } else {
            _Count = _Count2;
        }
    }

    _Seek_wrapped(_First, _UFirst);
    return _First;
}

这个函数比较麻烦,它返回的是第一个不满足_Pred条件的元素。这里_Pred条件是<,所以返回的是第一个大于等于这个元素的迭代器, 然后binary_search函数就用!(_Pred(_Val, *_Ufirst))这个条件来判断是否相等,这相当于构造了 \(a >= b\) \(a <= b\) 显然地,只有当$a == b$时,表达式才返回真(吐槽一下,这stl写的太“聪明”了)

在二分查找中,成功查找时的ASL为: \(\sum{i * P(i)} = 1/n*( \sum_{1}^{floor(log(n))}{i * 2^{i}} + ceil(log(n)) * (n - floor(log(n))))\) 这个式子过于繁琐,我们假设它的二叉判定树为满二叉树,可以得到: \({n - 1}/{n} * log(n + 1) - 1\)

分块查找

分块查找采用了块间有序,块内无序的基本思想,建立一个索引表记录块内的最大值或最小值,然后先查索引表,找到对应的块,然后再到块中查询。

stl中的deque实现有这种思想的影子。

堆/优先队列

堆的概念与实现

堆这个词来自于heap。我们最先学习到的heap,指的是C程序运行时环境的一部分–内存动态分配器及其分配的空间,我们在使用malloc函数、new函数(new实际上是一个函数)时都要用到它来分配空间。

但是这里的heap,指的是一种特殊的数据结构,它具有以下特点:

  • 分为小顶堆和大顶堆
  • 对自$0$至$floor(n/2) - 1$的元素$heap[i]$有 \(heap[i] <= heap[2i + 1]\) \(heap[i] <= heap[2i + 2]\)

其实,第二个特点表明堆可以化为一颗二叉树,这颗二叉树的父亲节点都大于它的子节点。

我们这里用ruby语言实现了一个简单的堆:

module BinaryHeapable
  def insert_to_heap element
    target = self.length
    while self[target / 2] < element && target != 0
      self[target] = self[target/2]
      target /= 2
    end
    self[target] = element
  end

  def remove_from_heap
    ret = self[0]
    self[0] = self[-1]
    self.pop
    heap_construct 0
    ret
  end
  
  def convert_to_heap
    i = self.length / 2 - 1
    while i >= 0
      heap_construct i
      i -= 1
    end
    self
  end

  private
  def heap_construct target
    what = 0
    while target * 2 + 1 < self.length
      if target * 2 + 2 < self.length
        what = self[target * 2 + 1] > self[target * 2 + 2] ? target * 2 + 1 : target * 2 + 2
      else
        what = target * 2 + 1
      end
      break if self[target] > self[what]
      temp = self[target]
      self[target] = self[what]
      self[what] = temp
      target = what
    end
    what
  end
end

ruby 中的module是mix-in思想的载体。只要我们让一个类include这个模块,这个类就获得了“堆化”的能力。特别地,ruby的数组被封装为Array类,而所有的自带类都是可以修改的:

class Array
  include BinaryHeapable
end 

这样一来,我们就可以按照以下方法使用数组:

arr = [3, 5, 3, 0, 8, 6, 1].convert_to_heap

while arr.length != 0
  pp arr.remove_from_heap
  pp arr
end

这段代码会打出:

8
[6, 5, 3, 0, 3, 1]
6
[5, 3, 3, 0, 1]
5
[3, 3, 1, 0]
3
[3, 0, 1]
3
[1, 0]
1
[0]
0
[]

在上面的代码中我们看到,堆只需要实现一个操作,就可以搞定建堆和取出堆顶。

这个操作是什么呢?就是如下的操作:

假设一个堆节点的左子树与右子树均已经满足堆序,把以这个堆节点为根的子树调整成堆序。

这个操作实现起来很简单,具体可参加代码。

实现了这个操作后,

  • 建堆就是自$floor(n/2) - 1$至$0$调用这个操作;
  • 取出堆顶就是先将堆顶缓存,再将堆尾和堆顶交换,再对堆顶调用这个操作。

堆可以用来做什么?

堆可以在$O(log(n))$的时间复杂度内完成取出最大/最小元素并调整,这一特性可以作以下用途:

  • 堆排序
  • 堆优化Dijkstra和Prim算法
  • 霍夫曼树的实现
  • etc

散列表

哈希表的定义

散列表,又称哈希表,是一种极为重要的数据结构。

为什么极其重要呢?因为

  • 上文提到的ruby,其内部数据结构有很大一部分是用散列表实现的。
  • 散列表可以用来建立映射,例如把一个字符串映射到一个整数上,这对某些情况是极为有用的(例如图结构笔记中实现的IndexMapping类)。

散列表的定义为:

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

哈希函数

首先必须明确,这里的哈希函数和密码学中的哈希函数实质是一样的,都是一个映射:

A hash function is any function that can be used to map data of arbitrary size to fixed-size values.

但是,这里的哈希函数和密码学中的哈希函数侧重点是不一样的:

密码学中的哈希函数主要要求两个性质:

  1. 均匀性,所有的输出是等概率
  2. 唯一性,要求单射,即是说不能存在$a,b$,使得$f(a) == f(b)$

高效性(速度)虽然很重要,但远远没有上面两条重要

而这里的哈希函数则要求高效性,因为我们访问哈希表中的元素可能是很频繁的。

所以密码学中的哈希函数用在这里是不太合适的。

教师讲述了6种方法,均以整数为键:

  1. 直接定址法(Identity hash function),找一个整数到整数的线性变换
  2. 折叠法(Folding),将整数分为几个部分,每个部分都是目标长度的倍数(最后一部分可以小于目标长度),然后将这几部分作运算(加、移位、异或等等),得到结果之后取目标长度位结果。
    • 密码学哈希算法多与这个方法类似
  3. 平方取中法(Mid-squares),先平方,然后取中间的目标长度位
  4. 除数余留法(Division hashing),直接取模
  5. 代数编码法(Algebraic coding),用数字的不同位作变换。
  6. 随机数法,不解释。

碰撞处理

如果发生了碰撞,也即是说,存在$a,b$,使得$f(a) == f(b)$,那么就需要进行处理,这大致有四种办法:

  1. 开放定址法
    • 线性探测法
    • 二次探测法
    • 随机探测法
  2. 再哈希法
  3. 链地址法
  4. 建立公共溢出区法 具体讨论略。

哈希表的实现 – 我实现的c++版本

/* hashtable.h */

#pragma once
#include <bits/stdc++.h>

#define TYPE_KEY char *
#define TYPE_VALUE char *
#define MD5 md5
#define NOT_FIND NULL
#define NUM_NOT_FIND -1

typedef uint64_t (*HASH_FUNC)(char *);
class HashTable
{
public:
    virtual bool insertTo(std::pair<TYPE_KEY, TYPE_VALUE> &pair) = 0;
    virtual bool deleteFrom(TYPE_KEY key) = 0;
    virtual uint64_t findByKey(TYPE_KEY key) = 0;
    virtual TYPE_VALUE getValueByKey(TYPE_KEY key) = 0;
};

template <typename T>
class LinkHashTableNode
{
public:
    T value;
    LinkHashTableNode *next;
    LinkHashTableNode(T value)
    {
        this->value = value;
        this->next = NULL;
    }
};

class LinkedHashTable : public HashTable
{
public:
    virtual bool insertTo(std::pair<TYPE_KEY, TYPE_VALUE> &pair);
    virtual bool deleteFrom(TYPE_KEY key);
    virtual TYPE_VALUE getValueByKey(TYPE_KEY key);
    LinkedHashTable(uint value, HASH_FUNC hashFunction);

private:
    virtual uint64_t findByKey(TYPE_KEY key);
    std::function<uint64_t(TYPE_KEY)> hash;
    std::vector<LinkHashTableNode<TYPE_VALUE> *> nodePool;
};
/* hashtable.cpp */

#include "./hashtable.h"
#include "md5.h"

LinkedHashTable::LinkedHashTable(uint size, HASH_FUNC hashFunction) : nodePool(size, NULL)
{
    this->hash = hashFunction;
}

uint64_t LinkedHashTable::findByKey(TYPE_KEY key)
{
    uint64_t hash_value = this->hash(key);
    hash_value = hash_value % this->nodePool.size();
    if (this->nodePool[hash_value] == NULL)
    {
        return NUM_NOT_FIND;
    }
    else
    {
        return hash_value;
    }
}

bool LinkedHashTable::insertTo(std::pair<TYPE_KEY, TYPE_VALUE> &pair)
{
    uint64_t hash_value = this->hash(pair.first);
    hash_value = hash_value % this->nodePool.size();
    auto new_node = new LinkHashTableNode<TYPE_VALUE>(pair.second);
    new_node->next = this->nodePool[hash_value];
    this->nodePool[hash_value] = new_node;
    return true;
}

bool LinkedHashTable::deleteFrom(TYPE_KEY key)
{
    auto hash_value = this->findByKey(key);
    if (hash_value == -1)
    {
        return false;
    }
    else
    {
        auto begin = this->nodePool[hash_value];
        this->nodePool[hash_value] = begin->next;
        delete begin;
        return true;
    }
}

TYPE_VALUE LinkedHashTable::getValueByKey(TYPE_KEY key)
{
    auto hash_value = this->findByKey(key);
    if (hash_value == NUM_NOT_FIND)
    {
        return NOT_FIND;
    }
    else
    {
        return this->nodePool[hash_value]->value;
    }
}

我们实现了一个很简单的哈希表,采用链地址法进行碰撞处理,采用MD5(这是一个密码学哈希函数)作为哈希函数。

Ruby中的哈希表实现

我们实现的哈希表,玩具色彩浓厚,特别是直接采用MD5算法这种愚蠢行为,每次查询时,都需要做至少64轮循环,效率是很差的。

所以,本笔记的最后一部分就集中精力来讨论一个工业级哈希表 – ruby中的哈希表。

ruby中的哈希表使用为:

hash = {:a => "haha", :b => "hahaha"}

这个数据结构在ruby程序中,使用得特别广泛、特别频繁。如果没有一个优秀的内部实现,ruby程序的性能将会受到很大影响。

笔记篇幅所限,这里不能完整地讨论ruby哈希表底层实现ruby/st.c中1000多行代码的全部内容。这里仅仅讨论一些最重要、和我们所学习内容关系最大的内容。

下面所称 st_table 指的就是ruby内部的哈希表

st_table 的哈希函数

/* ruby/st.c 537行 */
    hash_val = do_hash(key, table);

上面这段代码表明哈希函数就是do_hash.我们来看一下这个函数:

/* ruby/st.c 88行 */
#define do_hash(key,table) (st_index_t)(*(table)->type->hash)((key))

这段代码似乎不是很好理解,我们来一点点地看:

首先这是一个宏定义,传入两个参数key和table,给出一个值,其类型为st_index_t,也就是哈希表的具体位置(数组下标)

然后来看具体的内容

(*(table)->type->hash)((key))

这个语法其实是一个函数调用。(table)->type->hash是一个函数指针,指向hash函数,key是其参数。

那么想要找到真正的哈希函数,就必须要找到初始化时这个table->type->hash被赋了什么值:

哈希表的初始化有些复杂,但是为了讨论的方便还是介绍一下:

首先,所有的初始化都最终被转发到这个函数:

st_table*
st_init_table_with_size(const struct st_hash_type *type, st_index_t size)

然后实际使用时有三种初始化方法:

st_table*
st_init_numtable_with_size(st_index_t size)
{
    return st_init_table_with_size(&type_numhash, size);
}
st_table*
st_init_strtable_with_size(st_index_t size)
st_table*
st_init_strcasetable_with_size(st_index_t size)

我们这里只研究第一种st_init_numtable_with_size。这一种看名字就知道是整数对整数的映射。 它传入了一个type_numhash,这看起来是一个全局常量:

#define type_numhash st_hashtype_num
const struct st_hash_type st_hashtype_num = {
    st_numcmp,
    st_numhash,
};

那么,整数对整数的映射实际上应该调用到st_numhash这个函数:

/* ruby/st.c 1666 - 1683行 */
st_index_t
st_numhash(st_data_t n)
{
    /*
     * This hash function is lightly-tuned for Ruby.  Further tuning
     * should be possible.  Notes:
     *
     * - (n >> 3) alone is great for heap objects and OK for fixnum,
     *   however symbols perform poorly.
     * - (n >> (RUBY_SPECIAL_SHIFT+3)) was added to make symbols hash well,
     *   n.b.: +3 to remove ID scope, +1 worked well initially, too
     * - (n << 3) was finally added to avoid losing bits for fixnums
     * - avoid expensive modulo instructions, it is currently only
     *   shifts and bitmask operations.
     */
    return (st_index_t)((n>>(RUBY_SPECIAL_SHIFT+3)|(n<<3)) ^ (n>>3));
}

这个函数看起来倒是很简单,就是用n做了一些位运算。不过不属于教师讲述的6中方法之一。

这很大程度地激起了我的好奇心:难道Index是32位的整数吗?这个函数没有任何取模操作,如果传入一个很大的n,它该如何处理呢?

不要着急,让我们继续追踪吧:

/* ruby/st.c 584 - 588行 */
    if (ptr == 0) {
key = (*func)(key);
add_direct(table, key, value, hash_val, bin_pos);
return 0;
    }

我们注意到bin_pos这个参数,因为在add_direct函数中,它会调用new_entry函数,最后会执行这个语句:

/* ruby/st.c 445 行 */ 
entry->next = table->bins[bin_pos];
table->bins[bin_pos] = entry;

显然地,bin_pos才是数组查找的真正下标!那么bin_pos是在哪里被设置的呢?一个出乎预料的答案是在FIND_ENTRY宏中:

/* ruby/st.c 582行*/
    FIND_ENTRY(table, ptr, hash_val, bin_pos);
/* ruby/st.c 344行 */
#define FIND_ENTRY(table, ptr, hash_val, bin_pos) \
    ((ptr) = find_entry((table), key, (hash_val), ((bin_pos) = hash_pos(hash_val, (table)->num_bins))))

经历了千辛万苦,我们终于来到了真正获取下标的hash_pos宏:

/* ruby/st.c 89行 */
#define hash_pos(h,n) ((h) & (n - 1))

这里可以看到,实际的下标是和哈希表的长度与之后的结果。

有人可能会问,为什么要有两套键(一个hash_val,一个bin_pos)呢?我们下面会谈到,这里埋个伏笔。不过在谈到这个问题之前,我们先要看看它的碰撞处理。

st_table的碰撞处理

如果FIND_ENTRY宏找到了该key,st_table会如何处理呢?其实,这个问题在add_direct调用的new_enrty函数那里就可以看出来:

/* ruby/st.c 445 - 446行 */
    entry->next = table->bins[bin_pos];
    table->bins[bin_pos] = entry;

这写法显然是链表的头插法,所以是链地址法。

st_table的扩容

在我们实现的哈希表中,真正的哈希算法为: \(hash = MD5(key) \% n\) 这样一来带来一个很麻烦的问题 – 扩容时必须重新计算哈希值。

而我们可以猜想到,得益于ruby哈希表中hash_val和bin_pos的分离,扩容时只需要重新计算bin_pos,而不需要重新计算哈希值。

真的是这样吗?让我们再看看源代码:

/* ruby/st.c 459 - 462行 */
    if (table->num_entries > ST_DEFAULT_MAX_DENSITY * table->num_bins) {
rehash(table);
    bin_pos = hash_pos(hash_val, table->num_bins);
    }

可以清楚地看到,如果现在的哈希表项数大于可以容纳的最大数量 * 一个密度常数,那么就用rehash()函数重新对这个表作哈希,而rehash()函数定义如下:

/* ruby/st.c 609 - 627行 */
static void
rehash(register st_table *table)
{
    register st_table_entry *ptr, **new_bins;
    st_index_t new_num_bins, hash_val;

    new_num_bins = new_size(table->num_bins+1);
    new_bins = st_realloc_bins(table->bins, new_num_bins, table->num_bins);
    table->num_bins = new_num_bins;
    table->bins = new_bins;

    if ((ptr = table->head) != 0) {
	do {
	    hash_val = hash_pos(ptr->hash, new_num_bins);
	    ptr->next = new_bins[hash_val];
	    new_bins[hash_val] = ptr;
	} while ((ptr = ptr->fore) != 0);
    }
}

这段代码有两个地方需要研究

  1. new_size是如何实现的,新的大小和现大小是什么关系?
  2. 现在的哈希表是如何迁移到新的哈希表的?

首先研究第一个问题,我们直接研究new_size函数:

/* ruby/st.c 157 - 172行 */
static st_index_t
new_size(st_index_t size)
{
    st_index_t n;

    if (size && (size & ~(size - 1)) == size) /* already a power-of-two? */
	return size;

    n = next_pow2(size);
    if (n > size)
	return n;
#ifndef NOT_RUBY
    rb_raise(rb_eRuntimeError, "st_table too big");
#endif
    return -1;			/* should raise exception */
}

可以看到,下一个大小是next_pow2算出来的。也就是说,新的大小和旧的大小有如下关系: \(size_{new} = 2 \times size_{former}\)

然后研究第二个问题,现在的哈希表如何迁移到新的哈希表。

首先,st_realloc_bins只会重新分配内存,而不会迁移,真正的迁移在这个循环中进行:

if ((ptr = table->head) != 0) {
	do {
	    hash_val = hash_pos(ptr->hash, new_num_bins);
	    ptr->next = new_bins[hash_val];
	    new_bins[hash_val] = ptr;
	} while ((ptr = ptr->fore) != 0);
}

要说明白这个循环,必须认真研究一下st_table_entry:

/* ruby/st.c 18 - 26行 */
typedef struct st_table_entry st_table_entry;

struct st_table_entry {
    st_index_t hash;
    st_data_t key;
    st_data_t record;
    st_table_entry *next;
    st_table_entry *fore, *back;
};

这个next,指向的是本bin_pos的下一个项;而fore和back,实际上是把整个哈希表中所有的项做成了一个双向链表!

回过头来再看add_direct的最后一部分,我们会有种恍然大悟的感觉:

    if (table->head != 0) {
entry->fore = 0;
(entry->back = table->tail)->fore = entry;
table->tail = entry;
    }
    else {
table->head = table->tail = entry;
entry->fore = entry->back = 0;
    }

这也正是双向链表的插入操作,其中table->head是头指针,table->tail是尾指针。这样一来,所有的项都串成了一个双向链表,通过从头指针开始的遍历就可以将所有的项加入新的哈希表中,而这正是这个循环所做的事情:

do {
	hash_val = hash_pos(ptr->hash, new_num_bins);
	ptr->next = new_bins[hash_val];
	new_bins[hash_val] = ptr;
} while ((ptr = ptr->fore) != 0);

特别地,我们发现它确实只是将哈希值用hash_pos宏变为了bin_pos,即下标,从而避免了再次哈希键。

总结

总的来说,ruby中的哈希表有这几个特性:

  1. 哈希函数是将键做不循环的位运算。
  2. 哈希值和真正的下标分离,真正的下标由哈希值逻辑与哈希表长度得到,扩容时不需要再次计算哈希值,只需要再次计算真正的下标。
  3. 冲突处理采用链地址法。
  4. 容量永远是2的n次方,扩容时,新的容量是现容量的两倍
  5. 将所有的哈希表项用一个双向链表串起来,用头指针和尾指针实现对整个哈希表的高效遍历。