hashtable

hashtable

1. 这种结构在插入、删除搜寻等操作都具有常数平均时间的表现
2. hash function将大数映射为小数，避免索引过大
3. 为了避免不同元素被映射到相同的位置，使用线性探测、二次探测和开链法等

4. 以开链法完成的hashtable，每个单元的buckt涵盖的是linked list

   template <class value>
   struct __hashtable_node
   {
   	__hashtable_node* next;
   	Value val;
   }

5. hash table没有后退操作

6. bucket聚合体是以vector实现的
7. 头文件<stl_hash_func.h>定义了现成的hash function(bkt_num()等)计算元素位置，但是在客户端程序中不能包含这个头文件，应该含入有用到的hashtable的容器头文件<hash_set.h>或<hash_map.h>
8. SGI STL用质数来设计表格大小，将28个质数计算好，以备随时访问，提供一个函数开查询这28个质数中，最接近某数并大于某数的质数，next_size()，如50-53
9. hashtable函数

• new_node() 节点配置
• delete_node() 节点释放
• insert_unique() 插入不重复的元素，返回pair
• resize() 插入元素时可能需要重建hashtable
• insert_unique_noresize() 在不需要重建表格的情况下插入新节点，键值不允许重复
• insert_equal() 插入元素，允许重复
• insert_euqal_noresize() 在不需要重建表格的情况下插入新节点，键值允许重复
• bkt_num() 判断节点落脚处
• clear() 整体删除
• copy_from() 拷贝hashtable
• find() 寻找元素
• count() 查找元素的个数

10. hashtable的function不能处理string/double/float的元素，需要自己定义hash function

hash_set/hash_map

1. 转调用hashtable的操作行为
2. hashtable不支持的类型，hash_set也不支持
3. hash_map没有像map一样的自动排序功能
4. 函数：

• size()
• max_size()
• empty()
• swap()
• operator==
• begin() end()
• insert()
• find()
• count()
• equal_range()
• erase()
• clear()
• resize()
• bucket_count()
• max_bucket_count()
• elems_in_bucket()

5. hash_multiset特性与multiset完全相同，唯一的差别在于它的底层机制是hash_table，hash_multiset元素插入操作使用insert_equal()，multiset的元素插入操作采用insert_unique()
6. hash_multimap特性与multimap完全相同,唯一的差别在于它的底层机制是hash_table，hash_multimap元素插入操作使用insert_equal()，multimap的元素插入操作采用insert_unique()