Java數據結構中的常見問題總結

這篇文章主要介紹“Java數據結構中的常見問題總結”，在日常操作中，相信很多人在Java數據結構中的常見問題總結問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java數據結構中的常見問題總結”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

　　1、常用數據結構

　　數據結構是指相互之間存在著一種或多種關系的數據元素的集合和該集合中數據元素間的關系組成。常用的數據有：數組、棧、隊列、鏈表、樹、圖、堆、散列表。

　　1)數組：在內存中連續存儲多個元素的結構。數組元素通過下標訪問，下標從0開始。優點：訪問速度快;缺點：數組大小固定后無法擴容，只能存儲一種類型的數據，添加刪除操作慢。適用場景：適用于需頻繁查找，對存儲空間要求不高，很少添加刪除。

　　2)棧：一種特殊的線性表，只可以在棧頂操作，先進后出，從棧頂放入元素叫入棧，從棧頂取出元素叫出棧。應用場景：用于實現遞歸功能，如斐波那契數列。

　　3)隊列：一種線性表，在列表一端添加元素，另一端取出，先進先出。使用場景：多線程阻塞隊列管理中。

　　4)鏈表：物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表的指針地址實現，每個元素包含兩個結點，一個是存儲元素的數據域，一個是指向下一個結點地址的指針域。有單鏈表、雙向鏈表、循環鏈表。優點：可以任意加減元素，不需要初始化容量，添加刪除元素只需改變前后兩個元素結點的指針域即可。缺點：因為含有大量指針域，固占用空間大，查找耗時。適用場景：數據量小，需頻繁增加刪除操作。

　　5)樹：由n個有限節點組成一種具有層次關系的集合。二叉樹(每個結點最多有兩個子樹，結點的度最大為2，左子樹和右子樹有順序)、紅黑樹(HashMap底層源碼)、B+樹(mysql的數據庫索引結構)

　　6)散列表(哈希表)：根據鍵值對來存儲訪問。

　　7)堆：堆中某個節點的值總是不大于或不小于其父節點的值，堆總是一棵完全二叉樹。

　　8)圖：由結點的有窮集合V和邊的集合E組成。

　　2、并發集合了解哪些?

　　1)并發List，包括Vector和CopyOnWriteArrayList是兩個線程安全的List，Vector讀寫操作都用了同步，CopyOnWriteArrayList在寫的時候會復制一個副本，對副本寫，寫完用副本替換原值，讀時不需要同步。

　　2)并發Set，CopyOnWriteArraySet基于CopyOnWriteArrayList來實現的，不允許存在重復的對象。

　　3)并發Map，ConcurrentHashMap，內部實現了鎖分離，get操作是無鎖的。

　　4)并發Queue，ConcurrentLinkedQueue適用于高并發場景下的隊列，通過無鎖方式實現。 BlockingQueue阻塞隊列，應用場景，生產者-消費者模式，若生產快于消費，生產隊列裝滿時會阻塞，等待消費。

　　5)并發Deque, LinkedBlockingDueue沒有進行讀寫鎖分離，同一時間只能有一個線程對其操作。

　　6)并發鎖重入鎖ReentrantLock，互斥鎖，一次最多只能一個線程拿到鎖。

　　7)讀寫鎖ReadWriteLock，有讀取和寫入鎖兩種，讀取允許多個讀取線程同時持有，而寫入只能有一個線程持有。

　　3、列舉java的集合以及集合之間的繼承關系

　　1.單列表

　　2.雙列表

　　4、容器類介紹以及之間的區別

　　1)Collection接口：集合框架的根接口，它是集合類框架中最具一般性的頂層接口。

　　2)Map接口：提供了鍵值對的映射關系的集合，關鍵字不能有重復值，每個關鍵字至多可映射一個值。HashMap(通過散列機制，用于快速訪問)，TreeMap(保持key處于排序狀態，訪問速度不如hashmap), LinkedHashMap(保持元素的插入順序)

　　3)Set接口：不能包含重復的元素，LinkedHashSet TreeSet(用紅黑樹來存儲元素) HashSet

　　4)List接口:可通過索引對元素進行精準的插入和查找，實現類有ArrayList LinkedList

　　5)Queue接口：繼承自Collection接口，LinkedList實現了Queue接口，提供了支持隊列的行為。

　　6)Iterator接口：為了迭代集合

　　7)Comparable接口：用于比較

　　5、List,Set,Map的區別

　　Set是一個無序的集合，不能包含重復的元素;

　　list是一個有序的集合可以包含重復的元素，提供了按索引訪問的方式;

　　map包含了key-value對，map中key必須唯一，value可以重復。

　　6、HashMap的實現原理

　　1)數據結構

　　jdk1.7及以前，HashMap由數組+鏈表組成，數組Entry是HashMap的主體，Entry是HashMap中的一個靜態內部類，每一個Entry包含一個key-value鍵值對，鏈表是為解決哈希沖突而存在。

　　從jdk1.8起，HashMap是由數組+鏈表/紅黑樹組成，當某個bucket位置的鏈表長度達到閥值8時，這個鏈表就轉變成紅黑樹。

　　2)HashMap是線程不安全的，存儲比較快，能接受null值，HashMap通過put(key, value)來儲存元素，通過get(key)來得到value值，通過hash算法來計算hashcode值，用hashcode標識Entry在bucket中存儲的位置。

　　3)HashMap中為什么要使用加載因子，為什么要進行擴容

　　加載因子是指當HashMap中存儲的元素/最大空間值的閥值，如果超過這個值，就會進行擴容。加載因子是為了讓空間得到充分利用，如果加載因子太大，雖對空間利用更充分，但查找效率會降低;如果加載因子太小，表中的數據過于稀疏，很多空間還沒用就開始擴容，就會對空間造成浪費。

　　至于為什么要擴容，如果不擴容，HashMap中數組處的鏈表會越來越長，這樣查找效率就會大大降低。

　　6.1 HashMap如何put數據(從HashMap源碼角度講解)?

　　當我們使用put(key, value)存儲對象到HashMap中時，具體實現步驟如下：

　　1)先判斷table數組是否為空，為空以默認大小構建table，table默認空間大小為16

　　2)計算key的hash值，并計算hash&(n-1)值得到在數組中的位置index，如果該位置沒值即table[index]為空，則直接將該鍵值對存放在table[index]處。

　　3)如果table[index]處不為空，說明發生了hash沖突，判斷table[index]處結點是否是TreeNode(紅黑樹結點)類型數據，如果是則執行putTreeVal方法，按紅黑樹規則將鍵值對存入;

　　4)如果table[index]是鏈表形式，遍歷該鏈表上的數據，將該鍵值對放在table[index]處，并將其指向原index處的鏈表。判斷鏈表上的結點數是否大于鏈表最大結點限制(默認為8)，如果超過了需執行treeifyBin()操作，則要將該鏈表轉換成紅黑樹結構。

　　5)判斷HashMap中數據個數是否超過了(最大容量*裝載因子)，如果超過了，還需要對其進行擴容操作。

　　6.2 HashMap如何get數據?

　　get(key)方法獲取key的hash值，計算hash&(n-1)得到在鏈表數組中的位置first=table[hash&(n-1)]，先判斷first(即數組中的那個)的key是否與參數key相等，不等的話，判斷結點是否是TreeNode類型，是則調用getTreeNode(hash, key)從二叉樹中查找結點，不是TreeNode類型說明還是鏈表型，就遍歷鏈表找到相同的key值返回對應的value值即可。

　　6.3 當兩個對象的hashcode相同，即發生碰撞時，HashMap如何處理

　　當兩個對象的hashcode相同，它們的bucket位置相同，hashMap會用鏈表或是紅黑樹來存儲對象。Entry類里有一個next屬性，作用是指向下一個Entry。第一個鍵值對A進來，通過計算其key的hash得到index，記做Entry[index]=A。一會又進來一個鍵值對B，通過計算其key的hash也是index，HashMap會將B.next=A, Entry[index]=B.如果又進來C，其key的hash也是index,會將C.next=B, Entry[index]=C.這樣bucket為index的地方存放了A\B\C三個鍵值對，它們能過next屬性鏈在一起。數組中存儲的是最后插入的元素，其他元素都在后面的鏈表里。

　　6.4 如果兩個鍵的hashcode相同，如何獲取值對象?

　　當調用get方法時，hashmap會使用鍵對象的hashcode找到bucket位置，找到bucket位置后，會調用key.equals()方法去找到鏈表中正確的節點，最終找到值對象。

　　6.5 hashMap如何擴容

　　HashMap默認負載因為是0.75，當一個map填滿了75%的bucket時，和其他集合類一樣，將會創建原來HashMap大小兩倍的bucket數組，來重新調整HashMap的大小，并將原來的對象放入新的bucket數組中。

　　在jdk1.7及以前，多線程擴容可能出現死循環。因為在調整大小過程中，存儲在某個bucket位置中的鏈表元素次序會反過來，而多線程情況下可能某個線程翻轉完鏈表，另外一個線程又開始翻轉，條件競爭發生了，那么就死循環了。

　　而在jdk1.8中，會將原來鏈表結構保存至節點e中，將原來數組中的位置設為null，然后依次遍歷e，根據hash&n是否為0分成兩條支鏈，保存在新數組中。如果多線程情況可能會取到null值造成數據丟失。

　　7、ConcurrentHashMap的實現原理

　　1)jdk1.7及以前：一個ConcurrentHashMap由一個segment數組和多個HashEntry組成，每一個segment都包含一個HashEntry數組, Segment繼承ReentrantLock用來充當鎖角色，每一個segment包含了對自己的HashEntry的操作，如get\put\replace操作，這些操作發生時，對自己的HashEntry進行鎖定。由于每一個segment寫操作只鎖定自己的HashEntry，可以存在多個線程同時寫的情況。

　　jdk1.8以后：ConcurrentHashMap取消了segments字段，采用transient volatile HashEntry table保存數據，采用table數組元素作為鎖，實現對每一個數組數據進行加鎖，進一小減少并發沖突概率。ConcurrentHashMap是用Node數組+鏈表+紅黑樹數據結構來實現的，并發制定用synchronized和CAS操作。

　　2)Segment實現了ReentrantLock重入鎖，當執行put操作，會進行第一次key的hash來定位Segment的位置，若該Segment還沒有初始化，會通過CAS操作進行賦值，再進行第二次hash操作，找到相應的HashEntry位置。

　　8、ArrayMap和HashMap的對比

　　1)存儲方式不一樣，HashMap內部有一個Node[]對象，每個鍵值對都會存儲到這個對象里，當用put方法添加鍵值對時，會new一個Node對象，tab[i] = newNode(hash, key, value, next);

　　ArrayMap存儲則是由兩個數組來維護，int[] mHashes; Object[] mArray; mHashes數組中保存的是每一項的HashCode值，mArray存的是鍵值對，每兩個元素代表一個鍵值對，前面保存key，后面保存value。mHashes[index]=hash; mArray[index<<1]=key; mArray[(index<<1)+1]=value; 　　ArrayMap相對于HashMap，無需為每個鍵值對創建Node對象，且在數組中連續存放，更省空間。 　　2)添加數據時擴容處理不一樣，進行了new操作，重新創建對象，開銷很大;而ArrayMap用的是copy數據，所有效率相對高些; 　　3)ArrayMap提供了數組收縮功能，在clear或remove后，會重新收縮數組，釋放空間; 　　4)ArrayMap采用二分法查找，mHashes中的hash值是按照從小到大的順序連續存放的，通過二分查找來獲取對應hash下標index，去mArray中查找鍵值對。mHashes中的index2是mArray中的key下標，index2+1為value的下標，由于存在hash碰撞情況，二分查找到的下標可能是多個連續相同的hash值中的任意一個，此時需要用equals比對命中的key對象是否相等，不相等，應當從當前index先向后再向前遍歷所有相同hash值。 　　5)sparseArray比ArrayMap進一步優化空間，SparseArray專門對基本類型做了優化，Key只能是可排序的基本類型，如int\long，對value，除了泛型Value，還對每種基本類型有單獨實現，如SparseBooleanArray\SparseLongArray等。無需包裝，直接使用基本類型值，無需hash，直接使用基本類型值索引和判斷相等，無碰撞，無需調用hashCode方法，無需equals比較。SparseArray延遲刪除。 　　9、HashTable實現原理

　　Hashtable中的無參構造方法Hashtable()中調用了this(11, 0.75f)，說明它默認容量是11，加載因子是0.75,在構造方法上會new HashtableEntry[initialCapacity]; 會新建一個容量是初始容量的HashtableEntry數組。HashtableEntry數組中包含hash\Key\Value\next變量，鏈表形式，重寫了hashCode和equals方法。Hashtable所有public方法都在方法體上加上了synchronized鎖操作，說明它是線程安全的。它還實現了Serializable接口中的writeObject和readObject方法，分別實現了逐行讀取和寫入的功能，并且加了synchronized鎖操作。

　　(1) put(Key, Value)方法

　　1)先判斷value是否為空，為空拋出空指針異常;

　　2)根據key的hashCode()值，計算table表中的位置索引(hash&0x7FFFFFFF)%tab.length值index，如果該索引處有值，再判斷該索引處鏈表中是否包含相同的key，如果key值相同則替換舊值。

　　3)如果沒有相同的key值，調用addEntry方法，在addEntry中判斷count大小是否超過了最大容量限制，如果超過了需要重新rehash()，容量變成原來容量*2+1，將原表中的值都重新計算hash值放入新表中。再構造一個HashtableEntry對象放入相應的table表頭，如果原索引處有值，則將table[index].next指向原索引處的鏈表。

　　(2)get方法

　　根所key.hashCode()，計算它在table表中的位置，(hash&0x7FFFFFFF)%tab.length，遍歷該索引處表的位置中是否有值，是否存在鏈表，再判斷是key值和hash值是否相等，相等則返回對應的value值。

　　10、HashMap和HashTable的區別

　　1)Hashtable是個線程安全的類，在對外方法都添加了synchronized方法，序列化方法上也添加了synchronized同步鎖方法，而HashMap非線程安全。這也導致Hashtable的讀寫等操作比HashMap慢。

　　2)Hashtable不允許值和鍵為空，若為空會拋出空指針。而HashMap允許鍵和值為空;

　　3)Hashtable根據key值的hashCode計算索引，(hash&0x7FFFFFFF)%tab.length，保證hash值始終為正數且不超過表的長度。而HashMap中計算索引值是通過hash(key)&(tab.length-1)，是通過與操作，計算出在表中的位置會比Hashtable快。

　　4)Hashtable容量能為任意大于等于1的正數，而HashMap的容量必須為2^n，Hashtable默認容量為11，HashMap初始容量為16

　　5)Hashtable每次擴容，新容量為舊容量的2倍+1，而HashMap為舊容量的2倍。

　　11、HashMap與HashSet的區別

　　HashSet底層實現是HashMap,內部包含一個HashMap map變量

　　private transient HashMap map;

　　一個Object PRESENT變量(當成插入map中的value值)

　　private static final Object PRESENT = new Object();

　　HashSet中元素都存到HashMap鍵值對的Key上面。具體可以查看HashSet的add方法，直接調用了HashMap的put方法，將值作為HashMap的鍵，值用一個固定的PRESENT值。

　　public boolean add(E e) {

　　return map.put(e, PRESENT)==null;

　　}

　　HashSet沒有單獨的get方法，用的是HashMap的。HashSet實現了Set接口，不允許集合中出現重復元素，將對象存儲進HashSet前，要先確保對象重寫了hashCode()和equals方法，以保證放入set對象是唯一的。

　　12、HashSet與HashMap怎么判斷集合元素重復?

　　HashMap在放入key-value鍵值對是，先通過key計算其hashCode()值，再與tab.length-1做與操作，確定下標index處是否有值，如果有值，再調用key對象的equals方法，對象不同則插入到表頭，相同則覆蓋;

　　HashSet是將數據存放到HashMap的key中，HashMap是key-value形式的數據結構，它的key是唯一的，HashSet利用此原理保證放入的對象唯一性。

　　13、集合Set實現Hash怎么防止碰撞

　　HashSet底層實現是HashMap，HashMap如果兩個不同Key對象的hashCode()值相等，會用鏈表存儲，HashSet也一樣。

　　14、ArrayList和LinkedList的區別，以及應用場景

　　ArrayList底層是用數組實現的，隨著元素添加，其大小是動態增大的;在內存中是連續存放的;如果在集合末尾添加或刪除元素，所用時間是一致的，如果在列表中間添加或刪除元素，所用時間會大大增加。通過索引查找元素速度很快。適合場合：查詢比較多的場景

　　LinkedList底層是通過雙向鏈表實現的，LinkedList和ArrayList相比，增刪速度快，但查詢和修改值速度慢。在內存中不是連續內存。場景：增刪操作比較多的場景。

到此，關于“Java數據結構中的常見問題總結”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！