散列表的基本原理和實(shí)現(xiàn)
對(duì)于基于散列表實(shí)現(xiàn)的符號(hào)表，若我們要在其中查找一個(gè)鍵，需要進(jìn)行以下步驟：
1、首先我們使用散列函數(shù)將給定鍵轉(zhuǎn)化為一個(gè)“數(shù)組的索引”拯辙，理想情況下，不同的key會(huì)被轉(zhuǎn)為不同的索引颜价，但在實(shí)際應(yīng)用中我們會(huì)遇到不同的鍵轉(zhuǎn)為相同的索引的情況涯保，這種情況叫做碰撞。解決碰撞的方法我們后面會(huì)具體介紹周伦。
2夕春、得到了索引后，我們就可以像訪問數(shù)組一樣专挪，通過這個(gè)索引訪問到相應(yīng)的鍵值對(duì)及志。
以上就是散列表的核心思想，散列表是時(shí)空權(quán)衡的經(jīng)典例子寨腔。
當(dāng)我們的空間無限大時(shí)速侈，我們可以直接使用一個(gè)很大的數(shù)組來保存鍵值對(duì)，并用key作為數(shù)組索引迫卢，因?yàn)榭臻g不受限锌畸，所以我們的鍵的取值可以無窮大，因此查找任何鍵都只需進(jìn)行一次普通的數(shù)組訪問靖避。
反過來，若對(duì)查找操作沒有任何時(shí)間限制比默，我們就可以直接使用鏈表來保存所有鍵值對(duì)幻捏，這樣把空間的使用降到了最低，但查找時(shí)只能順序查找命咐。在實(shí)際的應(yīng)用中篡九，我們的時(shí)間和空間都是有限的，所以我們必須在兩者之間做出權(quán)衡醋奠，散列表就在時(shí)間和空間的使用上找到了一個(gè)很好的平衡點(diǎn)榛臼。
散列表的一個(gè)優(yōu)勢(shì)在于我們只需調(diào)整散列算法的相應(yīng)參數(shù)而無需對(duì)其他部分的代碼做任何修改就能夠在時(shí)間和空間的權(quán)衡上做出策略調(diào)整伊佃。
class R
{
int count;
public R(int count){
this.count = count;
}
public String toString(){
return "R[count:" + count + "]";
}
public boolean equals(Object obj){
if(this == obj)
return true;
if (obj != null && obj.getClass() == R.class) {
R r = (R)obj;
if (r.count == this.count) {
return true;
}
}
return false;
}
public int hashCode(){
return this.count;
}
}
對(duì)于集合中的所有元素 e
boolean contains(Object o){
return (o==null ? e==null : o.equals(e));
}
如果o為null,--〉如果e為null,返回為true,否則false
如果o不為null,--〉則返回o.equals(e)-->也就是如果o和e對(duì)象equal,返回true,否則false
getClass()相關(guān)
（在重寫equals()方法中用到），還有反射機(jī)制的介紹（沒看還）
http://blog.csdn.net/Ghost_T/article/details/5811974
Set的源碼分析
http://blog.csdn.net/lcore/article/details/8878893
hashCode()相關(guān) 講得很易懂啦
http://blog.csdn.net/lcore/article/details/8885022
關(guān)于HashMap的源碼分析 也講得不錯(cuò)
http://blog.csdn.net/lcore/article/details/8885961
Collection源碼學(xué)習(xí)
http://blog.csdn.net/lcore/article/details/8869937
List ArrayList類的源碼學(xué)習(xí)
http://blog.csdn.net/lcore/article/details/8872565
感覺博主這個(gè)系列做的很不錯(cuò)啦 20篇都值得去看下
