簡單了解下 HASH

不要問我大學數據結構課程在干嘛，我也不知道嘛。

只是突然把哈希表的哈希剝離出來，卻又覺得似曾相識。

在Ruby 中第一次見到 Hash ，當時納悶，有個這麼強大的數組，為什麼還要個哈希呢。

後來發現哈希的優勢在於查找，比如看這道題目：

 

求數組中出現次數最多的元素。

 

我是沒想到什麼好辦法，只能統計所有元素出現的次數，然後找出最大的那個。

這裡HASH的優勢就體現了出來，不過對於HASH的效率總是很困惑，以為它采用的是類似2分查找方法。

 

然後昨天簡單了解了下hash到底是什麼。

在搜索中最快的肯定是通過數組的下標來查找了，因為那是通過偏移來直接尋址的。

以前做算法設計時候，遇到簡單的排序我通常會這麼干

int a = {3,4,5,7,2,4,9,13,22,71,30} ;
int b[len] = {0}
for(int i=0;i<len;++i)
 b[a[i]]+=1;
for(int j=0;j<len;++j)
  if(b[j] != 0)
     printf("%d\t",b[j]);

 其實這個就是HASH大概的原理的，通過特定的算法吧hash轉換成線性表，主要的代價就是轉換復雜度和空間。

 我的收獲就是，放心使用HASH吧，效率決定一切！

 

 

寫到這裡，發現其實不自覺中已經使用多次了，在一個acm程序裡面，大概問題是九宮格拼圖游戲，求解從狀態1到狀態2最短需要幾步完成。我設計的方法是吧 九宮格的所有狀態 9!  映射到數組下標 ，然後在廣度搜索中挨個對比狀態最後求解。當時老師看了後，說你這算法好簡單好暴力。。。

 

大學4年馬上要走到尾聲了，漫無目的的尋覓，沒有好好玩也沒有好好學習過，曾更自己說從不後悔自己做的決定。

回顧這幾年，匆匆忙忙跑過去應付點名的場景一一再現，甚至是後來同學告訴我又被點名後無謂的表情。倔強不容許我後悔，C, algorithm, actionscript ， php  ， mfc, java , javascript ,ruby , design 都在嘗試，卻沒有一樣是有始有終的。朋友說，你只要堅持做一樣絕對會很好，事實是我真的捨不得丟棄我喜愛的玩具。

 

附找到的一些資料：

1 基本原理

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一 个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。

总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。

2 函数构造

构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：

a) 除余法：

选择一个适当的正整数 p ，令 h(k ) = k mod p
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。

b) 数字选择法：

如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。

3 冲突处理

线 性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。