前言
之前遇到一個(gè)問題枣申，具體是說： 當(dāng)我們用HashMap的時(shí)候茂契，是怎樣考慮優(yōu)化其性能的呢屡久？當(dāng)時(shí)就一臉懵逼忆首，原來是因?yàn)閔ashmap的自動(dòng)擴(kuò)容影響了性能，后面查資料才知道被环，可以通過設(shè)置hashmap的合理的初始容量或者加載因子來優(yōu)化糙及。 工作了一段時(shí)間了，連這個(gè)都不知道表示很羞愧筛欢。然后就去查看了一些關(guān)于數(shù)據(jù)結(jié)構(gòu)的知識(shí)浸锨。其實(shí)也常常聽說數(shù)據(jù)結(jié)構(gòu)包括鏈表唇聘，隊(duì)列，棧揣钦，樹和二叉樹雳灾，圖等。但是在java中具體的應(yīng)用有哪些呢冯凹？抱著一種好奇的心態(tài)去整列了一下java中的數(shù)據(jù)結(jié)構(gòu)谎亩。
大概整理如下圖
我在開發(fā)過程中用的最多的就屬hashmap和arrayList。樹和二叉樹看了很久還是不明所以宇姚，后面再逐步修改吧匈庭。
線性表
- linkedList 就是基于雙向鏈表的結(jié)構(gòu)其插入，刪除浑劳，新增的性能強(qiáng)于arrayList阱持。因?yàn)閍rrayList本質(zhì)就是數(shù)組,其需要的內(nèi)存空間必須是連續(xù)的，所以當(dāng)需要插入一條數(shù)據(jù)時(shí)魔熏，若在末端增加數(shù)據(jù)衷咽，其性能消耗也還好，但是若在任意位置插入就需移動(dòng)數(shù)據(jù)的位置蒜绽。linkedList 需要的內(nèi)存空間可以不連續(xù)镶骗，插入數(shù)據(jù)時(shí)只需要改變節(jié)點(diǎn)的prev和next的指向就行了。
- linkedList 隨機(jī)訪問get和set就沒有arrayList快了躲雅。linkedList需要移動(dòng)指針鼎姊。
- 棧 先進(jìn)后出，java中vector 是棧的應(yīng)用相赁，其線程安全相寇，性能差。其實(shí)現(xiàn)類是stack類
- 隊(duì)列 先進(jìn)先出钮科，java中的Queue是和List一樣繼承于collection唤衫。上圖用鏈表實(shí)現(xiàn)隊(duì)列的方法是用C語言實(shí)現(xiàn)，隊(duì)列最常見的應(yīng)用就是異步消息绵脯，日志等战授，如Android中的handler的messageQueue。
hash表（散列表）
java中的Map桨嫁。其中的實(shí)線類有 HashTable，HashMap份帐，WeakHashMap.其中weakhashMap是一種對(duì)key 弱引用map璃吧。寫到這里就想起了hashmap的原理以及hashmap與hashset的區(qū)別等，然后可以參看hashmap的原理
- hashTable 不允許null key和null value废境，線程安全畜挨，單線程操作性能差筒繁。 通過initial capacity和load factor兩個(gè)參數(shù)調(diào)整性能。通常缺省的load factor 0.75較好地實(shí)現(xiàn)了時(shí)間和空間的均衡巴元。增大load factor可以節(jié)省空間但相應(yīng)的查找時(shí)間將增大毡咏，這會(huì)影響像get和put這樣的操作。
- hashmap 允許null key和null value 但是是異步的逮刨，所以線程不安全呕缭。將HashMap視為Collection時(shí)（values()方法可返回Collection），其迭代子操作時(shí)間開銷和HashMap的容量成比例修己。因此恢总，如果迭代操作的性能相當(dāng)重要的話，不要將HashMap的初始化容量設(shè)得過高睬愤，或者load factor過低片仿。
樹和二叉樹
樹是一種非線性結(jié)構(gòu)，二叉樹為度為2的樹形結(jié)構(gòu)尤辱，分為左子樹和右子樹砂豌。
二叉樹概念以及存儲(chǔ)結(jié)構(gòu)--51CTO
- 葉結(jié)點(diǎn)（Leaf）：度為0的結(jié)點(diǎn)；
- 路徑和路徑長(zhǎng)度：從結(jié)點(diǎn)n1到nk的路徑為一個(gè)結(jié)點(diǎn)序列n1光督，n2阳距，...，nk可帽。ni是ni+1的父結(jié)點(diǎn)娄涩。路徑所包含邊的個(gè)數(shù)為路徑的長(zhǎng)度；
- 結(jié)點(diǎn)的層次（Level）：規(guī)定根結(jié)點(diǎn)在1層映跟，其他任一結(jié)點(diǎn)的層數(shù)是其父結(jié)點(diǎn)的層數(shù)加1
- 樹的深度（Depth）：樹中所有結(jié)點(diǎn)中的最大層次是這棵樹的深度蓄拣；
圖
圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G（V努隙，E）球恤，其中，G表示一個(gè)圖荸镊，V是圖G中頂點(diǎn)的集合咽斧，E是圖G中邊的集合。在圖中的數(shù)據(jù)元素躬存，我們稱之為頂點(diǎn)（Vertex）张惹，頂點(diǎn)集合有窮非空。在圖中岭洲，任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系宛逗，頂點(diǎn)之間的邏輯關(guān)系用邊來表示，邊集可以是空的盾剩。圖的詳解
樹和圖都沒有接觸過雷激，目前還不知道java中的應(yīng)用替蔬。
嘗試整理文章，每天進(jìn)步一丟丟屎暇，嘻嘻承桥。
