hash(散列)?

　　散列數(shù)據(jù)結(jié)構(gòu),但是java這里屏蔽了,直接就用封裝的形式把他封裝到了 HashSet,HashMap,HashTable中.其中HashTable已經(jīng)過時了.

　　hash算法:java中指的hashCode()函數(shù)及其重寫.

　　目標:給每個對象生成一個唯一的標示符

　　根據(jù)對象的特點為每個對象生成一個唯一hashCode,然后把這個hashCode作為下標,把對象值作為元素值保存到數(shù)組中(對象的引用).這個時候這個數(shù)組就可以看做關(guān)聯(lián)數(shù)組.java中沒有關(guān)聯(lián)數(shù)組這個概念,單獨取了個名叫HashSet.

Hash的過程:

　　拿到對象,調(diào)用他自己的hash算法(hashCode()方法),生成一個唯一的hash值,然后把這個值保存到數(shù)組中,整個過程就是hash.數(shù)組,和唯一值,和對象的關(guān)系,我們就叫HashSet;

　　hash算法在java中就是指Object中的hashCode()函數(shù)里面的算法,這一個是根據(jù)你寫的類來自己定義的.

　　hash哈希沖突:多個對象可能生成一個相同的hash值.

HashSet為什么無序,不可重復(fù)?

　　1 生成的hashCode沒有一定大小關(guān)系,就無所謂順序

　　2 每個對象都必須生成一個唯一的hashCode(多個對象可以生成相同的,但是還要比較值),如果是重復(fù)的對象,肯定是生成同一個hashCode,并且值也是相同的.這個時候就沒有辦法唯一性查詢出某個數(shù)據(jù).所以必須是不可重復(fù)的.所有的一切為了數(shù)據(jù)的唯一標識.

HashSet和HashMap

　　1 HashSet 是HashMap的一個實現(xiàn),本質(zhì)是HashMap.而HashMap的數(shù)據(jù)結(jié)構(gòu)是一個Hash表.

　　2 Hash表又叫散列表,其底層是通過hashCode()函數(shù)組成的一個數(shù)組,每個數(shù)組的元素又是一個單向鏈表.每個單項鏈表都有一個獨一無二hash值,就是數(shù)組的下標,也意味著每個單項鏈表的節(jié)點的hash值是相同的.

怎么向Hash表中添加元素.

　　1) 要添加的時候,HashMap保存的是映射關(guān)系,這個映射關(guān)系靠什么來維護(Map.Entry(K,V)),是一個接口,那我們就可以傳入各種對象的映射關(guān)系.如果生成了重復(fù)的hash值怎么辦?就會往HashTable,桶位上加一個單向鏈表單向鏈表中每個對象都是一個Entry.

　　重點:2) 添加過程: 第一步:先調(diào)用要存儲的映射關(guān)系的key對象,然后調(diào)用key對象自身的hashCode()方法,生成hash碼,向數(shù)組中添加元素.如果沒有這個hash碼,就占用一個數(shù)組的空間,保存這個key-value映射對象Entry.如果已經(jīng)有了這個hash碼,就需要執(zhí)行第二步.

　　第二步:equals(),把鍵的值挨個在hash碼相同的鏈表中進行比較,如果返回為true那么就代表該鏈表中已經(jīng)有了這個key值,就放棄添加,如果沒有則返回false,就執(zhí)行第三步.

　　第三步:就把數(shù)組中當(dāng)前保存的那個節(jié)點向后移動一位(并不是真的移動,只是我取得他內(nèi)存地址,保存在新加入的那個元素的nextNode中),再把當(dāng)前的這個映射關(guān)系對象Entry保存到數(shù)組中.

　　3) HashSet和Hashmap 初始化容量都是16,默認加載因子都是0.75.

索引數(shù)組:在內(nèi)存空間上是連續(xù)的記數(shù)也是連續(xù)的,總體就是有序的

關(guān)聯(lián)數(shù)組:在內(nèi)存空間上是連續(xù)的,記數(shù)不是連續(xù)的,就是無序的

哈希表:用hashCode()函數(shù)進行編碼的作為下標的關(guān)聯(lián)數(shù)組.

我們用的hashCode()函數(shù)可能會有重復(fù)的情況,但是數(shù)組又規(guī)定不能重復(fù),我們再用equals()比較另外一個外屬性(必須包含兩個比較,一個比較hashCode,另外一個比較另外一個屬性.)

hashSet:只保存了一個元素.

hashMap:是一個元素里面保存兩個對象的映射關(guān)系,再把這個映射關(guān)系封裝成一個對象