package da;
public class Main {
public static void main(String[] args) {
MyMap< String, String> mm = new MyMap< String, String>();
Long aBeginTime=System.currentTimeMillis();//記錄BeginTime
for(int i=0;i< 1000000;i++){
mm.put(""+i, ""+i*100);
}
Long aEndTime=System.currentTimeMillis();//記錄EndTime
System.out.println("insert time-->"+(aEndTime-aBeginTime));
Long lBeginTime=System.currentTimeMillis();//記錄BeginTime
mm.get(""+100000);
Long lEndTime=System.currentTimeMillis();//記錄EndTime
System.out.println("seach time--->"+(lEndTime-lBeginTime));
}
import java.util.Random;
String a[]={"李錦根","金行","成龍","客戶"};
Random s=new Random();
//int temp=s.nextInt();
int temp=(int) ((Math.random() * 3 + 1) * 1);
mm.put(""+i, ""+a[temp]);
//mm.put(""+100000000+i,""+"金");
System.out.println(i+a[temp]);
}
mm.put(""+100000000,""+"金");
//mm.get(""+3+a[0]);
//System.out.println(mm.get(""+100));
int coun=0;
for(int i=1;i< 1000000;i++){
//System.out.println(mm.get(""+i));
if(mm.get(""+i)!=null&&mm.get(""+i).equals("金行")){
coun++;
System.out.println(coun);
999958成龍
999959成龍
999960客戶
999961成龍
999962成龍
999963金行
999964成龍
999965成龍
999966金行
999967金行
999968成龍
999969金行
999970客戶
999971金行
999972成龍
999973客戶
999974成龍
999975客戶
999976客戶
999977金行
999978客戶
999979成龍
999980成龍
999981金行
999982客戶
999983成龍
999984成龍
999985客戶
999986成龍
999987金行
999988金行
999989客戶
999990金行
999991客戶
999992金行
999993金行
999994金行
999995成龍
999996客戶
999997成龍
999998金行
999999金行
insert time-->11621
219770
seach time--->430
探讨Hash表中的一些原理/概念，及根據這些原理/概念，自己設計一個用來存放/查找資料的Hash表，并且與JDK中的HashMap類進行比較。
我們分一下七個步驟來進行。
一。 Hash表概念
二 . Hash構造函數的方法，及适用範圍
三. Hash處理沖突方法，各自特征
四. Hash查找過程
五. 實作一個使用Hash存資料的場景--Hash查找算法，插入算法
六. JDK中HashMap的實作
七. Hash表與HashMap的對比，性能分析
一。 Hash表概念
在Hash表中，記錄在表中的位置和其關鍵字之間存在着一種确定的關系。這樣 我們就能預先知道所查關鍵字在表中的位置，進而直接通過下标找到記錄。
1) 哈希(Hash)函數是一個映象，即： 将關鍵字的集合映射到某個位址集合上，它的設定很靈活，
隻要這個位址集合的大小不超出允許範圍即可；
2) 由于哈希函數是一個壓縮映象，是以，在一般情況下，很容易産生“沖突”現象，
即： key1!=key2，而 f (key1) = f(key2)。
3). 隻能盡量減少沖突而不能完全避免沖突，這是因為通常關鍵字集合比較大，其元素包括所有可能的關鍵字，
而位址集合的元素僅為哈希表中的位址值.在構造這種特殊的“查找表” 時，除了需要選擇一個“好”(盡可能少産生沖突)
的哈希函數之外；還需要找到一 種“處理沖突” 的方法。
直接定址法
數字分析法
平方取中法
折疊法
除留餘數法
随機數法
（1）直接定址法：
哈希函數為關鍵字的線性函數，H(key) = key 或者 H(key) = a * key + b
（2）數字分析法：
假設關鍵字集合中的每個關鍵字都是由 s 位數字組成 (u1, u2, …, us)，分析關鍵字集中的全體，
并從中提取分布均勻的若幹位或它們的組合作為位址。
此法适于:能預先估計出全體關鍵字的每一位上各種數字出現的頻度。
（3）平方取中法：
以關鍵字的平方值的中間幾位作為存儲位址。求“關鍵字的平方值” 的目的是“擴大差别” ，
同 時平方值的中間各位又能受到整個關鍵字中各位的影響。
（4）折疊法：
将關鍵字分割成若幹部分，然後取它們的疊加和為哈希位址。兩種疊加處理的方法：移位疊加:
将分割後的幾部分低位對齊相加；間界疊加:從一端沿分割界來回折疊，然後對齊相加。
此法适于：關鍵字的數字位數特别多。
（5）除留餘數法：
設定哈希函數為:H(key) = key MOD p ( p≤m )，其中， m為表長，p 為不大于 m 的素數，或 是不含 20 以下的質因子
（6）随機數法：
設定哈希函數為:H(key) = Random(key)其中，Random 為僞随機函數
實際造表時，采用何種構造哈希函數的方法取決于建表的關鍵字集合的情況(包括關鍵字的範圍和形态)，
以及哈希表長度（哈希位址範圍），總的原則是使産生沖突的可能性降到盡可能地小。
“處理沖突” 的實際含義是：為産生沖突的關鍵字尋找下一個哈希位址。
開放定址法
再哈希法
鍊位址法
（1）開放定址法：
為産生沖突的關鍵字位址 H(key) 求得一個位址序列： H0, H1, H2, …, Hs 1≤s≤m-1，Hi = ( H(key) +di ) MOD m，
其中： i=1, 2, …, s，H(key)為哈希函數;m為哈希表長;
（2）鍊位址法：
将所有哈希位址相同的記錄都連結在同一連結清單中。
（3）再哈希法：
方法：構造若幹個哈希函數，當發生沖突時，根據另一個哈希函數計算下一個哈希位址，直到沖突不再發 生。
即：Hi=Rhi(key) i=1,2,……k，其中：Rhi——不同的哈希函數，特點：計算時間增加
對于給定值 K,計算哈希位址 i = H(K)，若 r[i] = NULL 則查找不成功，若 r[i].key = K 則查找成功，
否則 “求 下一位址 Hi” ，直至r[Hi] = NULL (查找不成功) 或r[Hi].key = K (查找成功) 為止。
五. 實作一個使用Hash存資料的場景-------Hash查找算法，插入算法
假設我們要設計的是一個用來儲存中南大學所有在校學生個人資訊的資料表。因為在校學生數量也不是特别巨大(8W)，
每個學生的學号是唯一的,是以，我們可以簡單的應用直接定址法，聲明一個10W大小的數組，每個學生的學号作為主鍵。
然後每次要添加或者查找學生，隻需要根據需要去操作即可。
但是，顯然這樣做是很腦殘的。這樣做系統的可拓展性和複用性就非常差了，比如有一天人數超過10W了？
如果是用來儲存别的資料呢？或者我隻需要儲存20條記錄呢？聲明大小為10W的數組顯然是太浪費了的。
如果我們是用來儲存大資料量（比如銀行的使用者數，4大的使用者數都應該有3-5億了吧？），這時候我們計算出來的
HashCode就很可能會有沖突了， 我們的系統應該有“處理沖突”的能力，此處我們通過挂鍊法“處理沖突”。
如果我們的資料量非常巨大，并且還持續在增加，如果我們僅僅隻是通過挂鍊法來處理沖突，可能我們的鍊上挂了
上萬個資料後，這個時候再通過靜态搜尋來查找連結清單，顯然性能也是非常低的。是以我們的系統應該還能實作自動擴容，
當容量達到某比例後，即自動擴容，使裝載因子儲存在一個固定的水準上。
綜上所述，我們對這個Hash容器的基本要求應該有如下幾點：
滿足Hash表的查找要求（廢話）
能支援從小資料量到大資料量的自動轉變（自動擴容）
使用挂鍊法解決沖突