java數(shù)據(jù)結(jié)構(gòu)面試題和答案

這篇文章為大家?guī)碛嘘P(guān)java數(shù)據(jù)結(jié)構(gòu)面試題和答案的詳細(xì)介紹。大部分面試題都是大家經(jīng)常見到的，為此分享給大家做個(gè)參考。一起跟隨小編過來看看吧。

【1、HashMap的工作原理？】

答：
A、HashMap基于Hashing原理，通過put()和get()方法存儲(chǔ)與獲取對(duì)象。
B、我們將值傳遞給put()方法，它調(diào)用鍵對(duì)象的hashCode()方法來計(jì)算hashcode，然后找到bucket位置來存儲(chǔ)對(duì)象。
C、獲取對(duì)象時(shí)，通過鍵對(duì)象的equals()方法找到正確的鍵值對(duì)，然后返回值對(duì)象。
D、HashMap使用鏈表來解決碰撞問題，當(dāng)發(fā)生碰撞了，對(duì)象將會(huì)儲(chǔ)存存在鏈表的下一個(gè)節(jié)點(diǎn)。
E、HashMap在每個(gè)鏈表節(jié)點(diǎn)中存儲(chǔ)鍵值對(duì)對(duì)象。

【2、什么是Hashing原理？】

散列法(Hashing)是一種將字符組成的字符換轉(zhuǎn)換為固定長度的數(shù)值或索引的方法，稱為散列法，也叫哈希法。
由于通過更短的哈希值比用原來的值進(jìn)行數(shù)據(jù)庫搜索更快，這種方法一般用在數(shù)據(jù)庫中建立索引進(jìn)行搜索，同時(shí)還用在各種解密算法中。

【3、HashMap中的bucket位置是什么？】

答：HashMap及其子類，采用Hash算法來決定集合中元素的存儲(chǔ)位置。當(dāng)系統(tǒng)開始初始化HashMap時(shí)，系統(tǒng)會(huì)創(chuàng)建一個(gè)長度為capacity的Entry數(shù)組。
這個(gè)數(shù)組里可以存儲(chǔ)元素的位置被稱為bucket（桶）。每個(gè)bucket都有指定索引，系統(tǒng)可以根據(jù)其索引快速訪問該bucket里存儲(chǔ)的元素。
HashMap的每個(gè)bucket（桶）只存儲(chǔ)一個(gè)元素Entry，由于Entry對(duì)象可以包含一個(gè)引用變量，也就是Entry指向另一個(gè)Entry依次類推，就形成了一個(gè)鏈。

【4、HashMap的讀取實(shí)現(xiàn)？】

答：當(dāng)HashMap的每個(gè)bucket里面只存儲(chǔ)一個(gè)Entry，也就是沒有通過指針產(chǎn)生Entry鏈時(shí)，此時(shí)HashMap具有最好的性能。
當(dāng)程序取出對(duì)應(yīng)的value時(shí)，系統(tǒng)只要先計(jì)算出key的hashcode返回值，根據(jù)hashode返回值找到該key在table數(shù)組中的索引，然后取出索引處的Entry，返回給可以對(duì)應(yīng)的value即可。

public V get(Object key) {   
 // 如果 key 是 null，調(diào)用 getForNullKey 取出對(duì)應(yīng)的 value   
 if (key == null)   
         return getForNullKey();   
 // 根據(jù)該 key 的 hashCode 值計(jì)算它的 hash 碼  
 int hash = hash(key.hashCode());   
 // 直接取出 table 數(shù)組中指定索引處的值，  
 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next){   
         Object k;   
         // 如果該 Entry 的 key 與被搜索 key 相同  
         if (e.hash == hash && ((k = e.key) == key   
                 || key.equals(k)))   
                 return e.value;   
 }   
 return null;   
}   

如果HashMap的每個(gè)桶里只有一個(gè)Entry時(shí)，HashMap可以根據(jù)索引快速的取出桶里的Entry。
在碰撞問題下，單個(gè)桶里存儲(chǔ)的不是一個(gè)Entry，而是一個(gè)Entry鏈，系統(tǒng)只有按順序遍歷每個(gè)Entry，知道找到目標(biāo)Entry為止。
HashMap在底層將key-value作為一個(gè)整體，進(jìn)行處理。這個(gè)整體就是Entry對(duì)象。HashMap底層采用一個(gè)Entry[]數(shù)組來保存所有的key-value。
當(dāng)需要存儲(chǔ)一個(gè)Entry對(duì)象時(shí)，會(huì)根據(jù)Hash算法來決定其存儲(chǔ)位置；
先判斷該位置上有沒有Entry，沒有的話就創(chuàng)建一個(gè)Entry對(duì)象，再在這個(gè)位置上插入；
如果有Entry的話，通過鏈表的遍歷方式去逐個(gè)遍歷，通過Equals方法將key和已有的key進(jìn)行比較，看看有沒有已經(jīng)存在的key，有的話用新的value替換之前的value；如果沒有則在table[i]插入該Entry，把原來的table[i]位置上的Entry賦值給新的Entry的next。所以新的Entry插入的位置永遠(yuǎn)是鏈表的最前面。
當(dāng)需要取出一個(gè)Entry對(duì)象時(shí)，會(huì)根據(jù)Hash算法找到其存儲(chǔ)位置，直接取出Entry。

【5、當(dāng)兩個(gè)不同的鍵對(duì)象的hashcode相同會(huì)怎樣？】

答：會(huì)儲(chǔ)存在同一個(gè)bucket位置的鏈表中。鍵對(duì)象的equals()方法用來找到鍵值對(duì)。

【6、什么是HashTable？】

答：哈希表（HashTable）又叫做散列表，是根據(jù)關(guān)鍵碼值（即鍵值對(duì)）而直接訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼映射到表中一個(gè)位置來訪問記錄，以加快查找速度

【7、HashMap和Hashtable的區(qū)別？】

答：1、繼承的父類不同
Hashtable繼承自Dictionary類，而HashMap繼承自AbstractMap類。但二者都實(shí)現(xiàn)了Map接口。
2、線程安全性不同
hashmap：此實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問一個(gè)哈希映射，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了該映射，則它必須保持外部同步。
HashMap和Hashtable都實(shí)現(xiàn)了Map接口，但決定用哪一個(gè)之前先要弄清楚它們之間的分別。主要的區(qū)別有：線程安全性，同步(synchronization)，以及速度。
HashMap幾乎可以等價(jià)于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行)。
HashMap是非synchronized，而Hashtable是synchronized，這意味著Hashtable是線程安全的，多個(gè)線程可以共享一個(gè)Hashtable；而如果沒有正確的同步的話，多個(gè)線程是不能共享HashMap的。
HashMap不能保證隨著時(shí)間的推移Map中的元素次序是不變的。
3、key和value是否允許null值
Hashtable中，key和value都不允許出現(xiàn)null值。
但是如果在Hashtable中有類似put(null,null)的操作，編譯同樣可以通過，因?yàn)閗ey和value都是Object類型，但運(yùn)行時(shí)會(huì)拋出NullPointerException異常，這是JDK的規(guī)范規(guī)定的。
HashMap中，null可以作為鍵，這樣的鍵只有一個(gè)；可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null。
當(dāng)get()方法返回null值時(shí)，可能是 HashMap中沒有該鍵，也可能使該鍵所對(duì)應(yīng)的值為null。因此，在HashMap中不能由get()方法來判斷HashMap中是否存在某個(gè)鍵， 而應(yīng)該用containsKey()方法來判斷。

【8、什么是HashSet？】

HashSet實(shí)現(xiàn)了Set接口，它不允許集合中有重復(fù)的值，當(dāng)我們提到HashSet時(shí)，第一件事情就是在將對(duì)象存儲(chǔ)在HashSet之前，要先確保對(duì)象重寫equals()和hashCode()方法，這樣才能比較對(duì)象的值是否相等，以確保set中沒有儲(chǔ)存相等的對(duì)象。如果我們沒有重寫這兩個(gè)方法，將會(huì)使用這個(gè)方法的默認(rèn)實(shí)現(xiàn)。public boolean add(Object o)方法用來在Set中添加元素，當(dāng)元素值重復(fù)時(shí)則會(huì)立即返回false，如果成功添加的話會(huì)返回true。

【9、HashMap與HashSet的區(qū)別？】

答：

【10、HashMap中的負(fù)載因子0.75是啥意思？】

答：HashMap中默認(rèn)的容量是16，負(fù)載因子為0.75。由于集合在使用的過程中，不斷的存放數(shù)據(jù)，當(dāng)存放的數(shù)量達(dá)到了16*0.75 = 12的時(shí)候就需要把當(dāng)前的16容量進(jìn)行擴(kuò)容。擴(kuò)容涉及到rehash，復(fù)制數(shù)據(jù)等操作，很消耗性能的。

【11、ConcurrentHashMap】

答：ConcurrentHashMap是Java中的一個(gè)線程安全且高效的HashMap實(shí)現(xiàn)。平時(shí)涉及高并發(fā)如果要用map結(jié)構(gòu)，那第一時(shí)間想到的就是它。
1、ConcurrentHashMap在JDK8里結(jié)構(gòu)：

它的優(yōu)點(diǎn)：結(jié)合了HashMap和HashTable。
它的兩個(gè)靜態(tài)內(nèi)部類：HsahEntry和segment
它含有16個(gè)segment： ConcurrentHashMap將hash表分為16個(gè)桶（默認(rèn)值），諸如get,put,remove等常用操作只鎖當(dāng)前需要用到的桶。
它的get方法：count>0,hash找到HashEntry,hash相等并且key相同，若取value為null，加鎖重新獲取。
它的remove方法：加鎖，每刪除一個(gè)元素就將那之前的元素克隆一邊。因?yàn)樵O(shè)置為第一次next之后不能再改變。
它的size（）方法：2次不鎖住segment方式統(tǒng)計(jì)各個(gè)segment的大小，若count發(fā)生變化，采用加鎖方式統(tǒng)計(jì)。modCount變量，在put，remove和clean方法里操作元素，modcount加1.

【12、什么是紅黑樹算法？】

答： 紅黑樹又稱紅-黑二叉樹，它首先是一顆二叉樹，它具體二叉樹所有的特性。同時(shí)紅黑樹更是一顆自平衡的排序二叉樹。
基本的二叉樹都需要滿足一個(gè)基本性質(zhì)，樹中的任何節(jié)點(diǎn)的值大于它的左側(cè)子節(jié)點(diǎn)，且小于右側(cè)子節(jié)點(diǎn)，這樣使得樹的檢索效率大大提高。
但是二叉樹非常容易失衡（一邊倒），這樣會(huì)導(dǎo)致檢索效率大大降低。因此出現(xiàn)了一系列的算法，像：AVL、SBT、伸展樹、TREAP、紅黑樹等。
這樣二叉樹就平衡了，它的左右兩個(gè)子樹的高度差絕對(duì)值不超過1，左右都是一顆平衡二叉樹?！竞罄m(xù)跟進(jìn)此類型的算法...】

【13、什么是TreeMap？】

答：TreeMap繼承AbstractMap，實(shí)現(xiàn)NavigableMap、Cloneable、Serializable三個(gè)接口。其中AbstractMap表明TreeMap為一個(gè)Map即支持key-value的集合， NavigableMap（更多）則意味著它支持一系列的導(dǎo)航方法，具備針對(duì)給定搜索目標(biāo)返回最接近匹配項(xiàng)的導(dǎo)航方法 。
【1】TreeMap中的元素默認(rèn)按照keys的自然排序排列。（對(duì)Integer來說，其自然排序就是數(shù)字的升序；對(duì)String來說，其自然排序就是按照字母表排序）

//創(chuàng)建一個(gè)空集合，按照自然順序排列
     TreeMap<Integer, String> treeMap = new TreeMap<>();
     //創(chuàng)建一個(gè)空TreeMap，按照指定的comparator排序
    TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder());
    map.put(3, "val");
    map.put(2, "val");
    map.put(1, "val");
    map.put(5, "val");
    map.put(4, "val");
    System.out.println(map); // {5=val, 4=val, 3=val, 2=val, 1=val}

     //map創(chuàng)建一個(gè)TreeMap，keys按照自然排序
     Map<Integer, String> map = new HashMap<>();
     map.put(1, "val");
     map.put(1, "val");
     map.put(5, "val");
        map.put(4, "val");
    TreeMap<Integer, String> treeMap = new TreeMap<>(map);

以上就是java數(shù)據(jù)結(jié)構(gòu)面試題和答案的詳細(xì)內(nèi)容了，看完之后是否有所收獲呢？如果想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊！