时雨の记-RainCode
远野嘉一(Lams Lupin)的专栏
posts - 2,  comments - 8,  trackbacks - 0
前言
      散列表(HashTable)又称为哈希表,是一种快速的数据查找结构,它通常是为一个(组)要记录的数据设计一个哈希函数H(x),依据这个函数进行给数据定位,如果是闭散列,那就是直接存到数组的H(x)下标处,如果是开散列,就是存到指针数组H(x)下标的链表处。在OI中某些Pascaler为了避开链表而采用的闭散列鄙人认为相当糟糕,至于原因会在后面解释。所以本文只谈开散列。

哈希表的组织方式:
      我们首先要确定一个哈希函数H(x),x是要记录的对象,我们以H(x)来确定对象的记录的链的位置。
      还需要一个指针数组来存放每个链的头指针。由于要使用链表,所以还要有一个class/struct作为链表的基本单位。
哈希表的一般实现:
首先是链表的基本元素:
template<class T>
struct t_node
{
    
public:
        T key;
        
//other info
        t_node* next;
}
;

然后是HashTable类的骨架(我在这里把它封装成类了):

template<class T>
class hashtable
{
    
public:
        hashtable();
        
int hash(const T &sr);
        
void insert();
        t_node 
*find(const T &sr);
        
//add more functions
    private:
        t_node 
*ht[t_size];//you should define t_size as sth before
        
//add more things
}
;

接下来是构造函数:

hashtable<T>::hahstable()
{
    memset(ht,
0,sizeof(ht));
}

先略去哈希函数,介绍插入函数:

void hashtable<T>::insert(const T &sr)
{
    
int loc = hash(sr);
    
if (ht[loc] == 0)
    
{
        
//此处为空,插入一个新链表
        ht[loc] = new t_node();
        ht[loc]
-> key = T;
    }

    
else
    
{
        t_node 
*now = ht[loc];
        
while (true)
        
{
            
if (now->key == sr)
            
{
                
//元素已经存在。 
                return;
            }

            
else if (now->next == 0)
            
{
                
//链里面没有该元素,就地插入
                now->next = new t_node();
                now
->next->key = T; 
                
return;
            }

            
else now = now->next;
        }

    }

}

然后是查找:

t_node *hashtable<T>::find(const T &st)
{
    
int loc = hash(sr);
    
if (ht[loc] == 0)
    
{
        
//此处为空,木有~ 返回空指针 
        return 0;
    }

    
else
    
{
        t_node 
*now = ht[loc];
        
while (true)
        
{
            
if (now->key == sr)
            
{
                
//找到了 
                return now;
            }

            
else if (now->next == 0)
            
{
                
//遍历完了整个链还是木有。。 
                return 0;
            }

            
else now = now->next;//看这个链的下一个元素 
        }

    }

}

当然可以根据具体情况做各种改动,如果要极限追求效率可以在t_node里面把key改为指针,然后使用自己编写的内存分配函数代替new。


最简单的哈希函数:
其实最简单的哈希表1就是H(x)=x,意思是若记录对象是整数,就直接采用这个整数为下标(char类型也可视为整数),这个就是数组,但它也可以看作哈希表。
最简单的哈希表2就是H(x)=1,意思是不管是什么元素都放到同一个下标,这个就是链表,也可视为一种哈希表。

大整数的哈希函数:
当记录对象是大整数的时候,若再用H(x)=x,数组的范围将会承受不起,所以这时候要考虑哈希函数的设计问题,又有很多种设计方法,最广泛的一种就是H(x)=x%k,k通常是一个质数。

一般的哈希函数:
我们也许会记录一些class或者struct之类的东西,这时候我们可以选取里面的某些关键变量进行一种运算来确定下标。

冲突的处理:
再好的哈希函数也很难避免冲突,所谓冲突就是说H(a)=H(b)的情况,而开散列的处理方法是在数组后面挂的是链表,这样冲突的元素可以直接挂在链表的末端,而闭散列没有链表,一般是重复Hn(x)或者往H(x)+a(a=1,2,3..)寻找,这会使哈希表变得一塌糊涂,而且冲突还可能引发别的冲突,而且也不便于估计哈希数组的范围,所以鄙人不提倡使用闭散列的组织方式。
顺便说一句:好的哈希函数是尽量减少和平衡冲突,尽量使得每个链的长度分布得平均,好的哈希函数的设计要靠长久的经验积累,绝非一日之功。

哈希表的本质思想:
散列表本质思想就是把数组与链表的优势结合起来,数组的访问复杂度是O(1),链表的插入复杂度是O(1),然而数组的插入复杂度和链表的访问复杂度都比较高,所以就产生了散列表。我们可以把这个思想运用到许多地方,这本是我想说的重点,但鄙人才疏学浅,不知如何表达,日后整理一下代码说明吧。

posted on 2011-09-10 12:07 远野嘉一 阅读(2723) 评论(8)  编辑 收藏 引用

FeedBack:
# re: 浅谈哈希思想的应用
2011-09-10 15:23 | 李立强
在CSDN的群里看到了,过来看看。
我觉得你在类中使用typedef会比较好,这样子不仅可以跟STL达到一种同步,同时可以方便的阅读和使用,例如可以把
typedef T size_type;
typedef size_type* iterator;
typedef const iterator const_iterator;
typedef size_type& reference;
typedef const reference const_reference;
之类的。这只是举例子,并不是一定适合你这个类,你可以自己写适合的typedef。还有一点,我在看primer时,他们将t_node设为class,然后再设置一个友元,这样子可以防止t_node的访问,达到封装的效果。  回复  更多评论
  
# re: 浅谈哈希思想的应用
2011-09-10 15:39 | 博洋家纺
止t_node的访问,达到封装的效果  回复  更多评论
  
# re: 浅谈哈希思想的应用[未登录]
2011-09-10 16:50 | Chipset
1、耗费内存太多。
2、速度可能不会太快。

作为对比,SGI STL和Boost的哈西表速度太慢,耗费内存也太多,估计你的这个还赶不上Boost和SGI STL的哈希表。如果感兴趣,到我的主页上看看哈西表怎么设计的。  回复  更多评论
  
# re: 浅谈哈希思想的应用
2011-09-10 19:49 | 远野嘉一
@Chipset
谢谢批评,你的哈希表我刚刚看了,确实不错。事实上我在编写哈希表的时候都是指针处理数据的,所以理论上在有N个元素时内存占用只有sizeof(ht)+N*sizeof(void*)以及N*sizeof(T)的数据原本占用的内存,sizeof(ht)=t_size*sizeof(void*),鄙人以为应该不会很高,此外我也通常自己编写内存管理器,和你的博文比较以后,发现我通常写的和你写的“拉链哈希”应当是时间、空间差不多的,还没发现新的东西。
至于哈希函数的设计和内存管理器我将会专门发文,所以在这里就没有赘述,愿今后继续关注、指教,谢谢!  回复  更多评论
  
# re: 浅谈哈希思想的应用
2011-09-10 19:52 | 远野嘉一
@李立强
谢谢建议,这个typedef加上应该是很好的,至于封装问题我以为是具体操作的事情了,应该不用赘述所以就没讲。。。以后会注意。  回复  更多评论
  
# re: 浅谈哈希思想的应用[未登录]
2011-09-10 21:26 | Chipset
@远野嘉一
不是批评,而是交流心得或者说互相学习。我说话不会拐弯抹角客气,请不要见怪。

你给出的信息比较少,我个人觉得t_size不应定义成常数,对于静态表初始化时指定容量就行了,如果是动态表应该能自动调整大小。

映射到一个数组时(对应下标),最好不要用取模,因为取模耗费太多CPU指令。
  回复  更多评论
  
# re: 浅谈哈希思想的应用[未登录]
2011-09-11 00:01 | Jcily
我倒是觉得博主说的言简意赅,非常节约读者时间又把信息传达到了。
顶一个。  回复  更多评论
  
# re: 浅谈哈希思想的应用[未登录]
2011-10-04 23:19 | Hero
文章言简意赅,建议代码用Coure New 字体,看起来舒服些。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

常用链接

留言簿

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜