Module: CodeCook::Find::HashSet

Defined in:

手写代码必备手册(Ruby版).rb

Overview

Defined Under Namespace

Classes: HashSetT

Constant Summary

HASH_SET_CAPACITY =

哈希表容量,一定要大于元素最大个数

100001

PRIME =

哈希表取模的质数,也即哈希桶的个数,小于 HASH_SET_CAPACITY.

99997

Class Method Summary (collapse)

• + (HashSetT) hash_set_create(hash, cmp)

  创建一个哈希集合.

• + (Boolean) hash_set_find(set, elem)

  查找某个元素是否存在.

Instance Method Summary (collapse)

• - (Boolean) hash_set_add(set, elem)

  添加一个元素,如果已存在则添加失败.

235
236
237
238
239
240
241

# File '手写代码必备手册(Ruby版).rb', line 235

def self.hash_set_create(hash, cmp)
    result = HashSetT.new
    result.size = 0
    result.hash = hash
    result.cmp = cmp
    result
end

248
249
250
251
252
253
254
255
256
257

# File '手写代码必备手册(Ruby版).rb', line 248

def self.hash_set_find(set, elem)
    hash = set.hash.call(elem)
    while (i = set.head[hash] and i != -1)
        if set.cmp.call(elem, set.node[i].elem)
            return true
        end
        i = set.node[i].next
    end
    return false
end

264
265
266
267
268
269
270
271
272
273
274
275
276

# File '手写代码必备手册(Ruby版).rb', line 264

def hash_set_add(set, elem)
    hash = set.hash.call(elem)
    while (i = set.head[hash] and i != -1)
        if set.cmp.call(elem, set.node[i].elem)
            return false
        end
        i = set.node[i].next
    end
    set.node[set.size].next = set.head[hash]
    set.node[set.size].elem = elem
    set.head[hash] = (set.size+=1)
    return true
end