内部一肖中特码:Java中那些常見概念總結 [復制鏈接]

2019-5-23 15:18
hackest 閱讀:244 評論:1 贊:0
Tag:  

1.HashMap和HashTable的區別

  • 致富之地一肖中特 www.qcfmo.icu [x] HashMap去掉了contains方法

  • [x] HashTable是同步的(線程安全)

  • [x] HashMap允許空鍵值

  • [x] HashMap執行快速失敗機制

  • [ ] Fast-fail機制:在使用迭代器的過程中有其它線程修改了集合對象結構或元素數量,都將拋出ConcurrentModifiedException

  • HashMap幾乎可以等價于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受為null的鍵值(key)和值(value),而Hashtable則不行)。

  • Hashtable和HashMap有幾個主要的不同:線程安全以及速度。僅在你需要完全的線程安全的時候使用Hashtable,而如果你使用Java 5或以上的話,請使用ConcurrentHashMap吧。

2.java的線程安全類

Vector、Stack、HashTable、ConcurrentHashMap、Properties

3.java集合框架

Collection - List

  • 有順序以線性方式存儲,可以存放重復對象

Collection - List - ArrayList

  • 數組方式存儲數據  索引數據快插入數據慢  線程不安全

Collection - List - LinkedList

  • 雙向鏈表實現存儲  索引數據慢插入數度較快  線程不安全(比安全性能好)

Collection - List - Vector

  • 數組方式存儲數據  索引數據快插入數據慢  線程安全

Collection - List - Vector - Stack

  • 繼承自Vector,實現一個后進先出的堆棧

Collection - Set

  • 無順序,不包含重復的元素

Collection - Set - HashSet

  • 為快速查找設計的Set。存入HashSet的對象必須定義hashCode()。

Collection - Set - TreeSet

  • 保存次序的Set, 底層為樹結構。使用它可以從Set中提取有序的序列。

Collection - Set - LinkedHashSet

  • 具有HashSet的查詢速度,且內部使用鏈表維護元素的順序(插入的次序)。于是在使用迭代器遍歷Set時,結果會按元素插入的次序顯示。

Map

  • 鍵必須是唯一

Map - HashMap

  • HashMap:基于散列表的實現  允許空鍵空值  線程不安全  (與Hashtable基本一致)

Map - TreeMap

  • TreeMap: 基于紅黑樹數據結構的實現  不允許空鍵空值  線程不安全

Map - HashTable

  • Hashtable:基于散列表的實現  允許空鍵空值  線程安全

Map - WeakHashMap

  • 改進的HashMap,它對key實行“弱引用”,如果一個key不再被外部所引用,那么該key可以被GC回收。

Map - LinkedHashMap

  • 具有HashMap的所有特性。

  • 內部對數據的存儲也是數組加鏈表的形式。

  • 多了一個雙向鏈表來維護內部數據的順序關系。

SparseArray

  • 采用了二分法方式存儲數據(安卓的一個集合類)

  • key必須為int類型,這中情況下的HashMap可以用SparseArray代替

  • 避免了HashMap自動裝箱得到內存消耗

ArrayMap

  • ArrayMap 實現了implements Map<K, V>接口,所以它也是一個關聯數組、哈希表。

  • 存儲以key->value 結構形式的數據。

  • 它也是線程不安全的,允許key為null,value為null。

  • 內部實現是基于兩個數組。

  • 一個int[]數組,用于保存每個item的hashCode.

  • 一個Object[]數組,保存key/value鍵值對。容量是上一個數組的兩倍。

  • 使用二分查找法得到相應的index

在除需要排序時使用TreeSet,TreeMap外,都應使用HashSet,HashMap,因為他們的效率更高。

3.1 ArrayList的構造函數有三個

  • 無參構造 容量為10

  • ArrayList(Collections<?extends E> c)構造包含指定collection的元素的列表

  • ArrayList(int initialCapacity) 指定初始容量

3.2 Iterator(迭代器)支持從源集合安全地刪除對象,防止并發修改異常(ConcurrentModifiedException)

4.Java垃圾回收機制

4.1 調用system.gc() Runtime.getRuntime.gc()

4.2 垃圾回收:釋放那些不再持有任何引用的對象的內存

4.3 怎樣判斷是否需要收集:

  • 引用計數法:對象沒有任何引用與之關聯(無法解決循環引用)

  • 對象引用遍歷法:對象引用遍歷從一組對象開始,沿著對象圖的每條鏈接,遞歸確定可以到達的對象,如果某對象不能從這些根對象的一個(至少一個)到達,則將它作為垃圾收集。

4.4 垃圾回收方法

  • 標記清除法(Mark-Sweeping):易產生內存碎片

  • 復制回收法(Copying):為了解決Mark-Sweep法而提出,內存空間減至一半

  • 標記壓縮法(Mark-Compact):為了解決Copying法的缺陷,標記后移動到一端再清楚

  • 分代回收法(GenerationalCollection):新生代對象存活周期短,需要大量回收對象,需要復制的少,執行copying算法;老年代對象存活周期相對長,回收少量對象,執行mark-compact算法.
    新生代劃分:較大的eden區 和 2個survivor區

4.5 內存分配

  • 新生代 |Eden Space|From Space|To Space|

  • 對象主要分配在新生代的EdenSpace和FromSpace

  • 如果EdenSapce和FromSpace空間不足,則發起一次GC

  • 若進行GC后,EdenSpace和FromSpace能夠容納該對象,就放在Eden和FromSpace。在GC過程中會將EdenSpace和FromSpace存活的對象移動到ToSpace,然后清理Eden和From。若在清理過程中,ToSpace無法足夠容納該對象,則將該對象移入老年代中。在進行GC后,Eden和From為空,MinorGC完成。From和To標記互換。To區(邏輯上)始終為空。

  • 新生代的回收成為MinorGC,對老年代的回收成為MajorGC又名FullGC

其他

  • 優先在Eden上分配

  • 大對象直接進入老年代

  • 長期存活的對象進入老年代

  • 動態對象年齡判定 suvivor區同年齡對象總和大于suvivor區空間的一半,MinorGC時復制至老年代

  • 空間分配擔保 新生代放不下借用老年代,虛擬機檢測GC租借的老年代內存是否大于剩余的老年代內存。若大于,MinorGC變為一次FullGC。若小于,查看虛擬機是否允許擔保失敗,若允許則執行一次MinorGC,否則也要變為一次FullGC

5.一些重要的關鍵字

  • volatile
    Java 語言提供了一種稍弱的同步機制,即volatile變量.用來確保將變量的更新操作通知到其他線程,保證了新值能立即同步到主內存,以及每次使用前立即從主內存刷新。 當把變量聲明為volatile類型后,編譯器與運行時都會注意到這個變量是共享的。volatile修飾變量,每次被線程訪問時強迫其從主內存重讀該值,修改后再寫回共享內存。保證讀取的可見性,對其他線程立即可見。由于不保證原子性,也就不能保證線程安全。由于及時更新,很可能導致另一線程訪問最新變量值,無法跳出循環的情況。同時,volatile屏蔽了VM中必要的代碼優化,效率上較低。另一個優點:禁止指令重排序

  • final
    final修飾的變量是常量,必須進行初始化,可以顯示初始化,也可以通過構造進行初始化,如果不初始化編譯會報錯。

6.多線程 & 并發 & 同步 & 鎖

6.1 線程的run方法和start方法

  • start方法
    用start方法來啟動線程,是真正實現了多線程。調用thread類的start方法來啟動一個線程,此時線程處于就緒狀態,一旦得到cpu時間片,就開始執行run方法。注:此時無需等待run方法執行完畢,即可執行下面的代碼,所以run方法并沒有實現多線程。

  • run方法
    只是thread類的一個普通方法,若直接調用程序中依然只有主線程這一個線程,還要順序執行,依然要等待run方法體執行完畢才可執行下面的代碼。

6.2 ReadWriteLock(讀寫鎖)

寫寫互斥 讀寫互斥 讀讀并發
在讀多寫少的情況下可以提高效率

6.3 resume(繼續掛起的線程)和suspend(掛起線程)一起用

6.4 wait與notify、notifyall一起用

6.5 sleep與wait的異同點

  • sleep是Thread類的靜態方法,wait來自object類

  • sleep不釋放鎖,wait釋放鎖

  • wait,notify,notifyall必須在同步代碼塊中使用,sleep可以在任何地方使用

  • 都可以拋出InterruptedException

6.6 讓一個線程停止執行

異常 - 停止執行
休眠 - 停止執行
阻塞 - 停止執行

6.7 ThreadLocal相關

ThreadLocal解決了變量并發訪問的沖突問題

  • 當使用ThreadLocal維護變量時,ThreadLocal為每個使用該變量的線程提供獨立的變量副本,每個線程都可以獨立地改變自己的副本,而不會影響其它線程所對應的副本,是線程隔離的。線程隔離的秘密在于ThreadLocalMap類(ThreadLocal的靜態內部類)

  • 原理

  • 這個類之所以能夠存儲每個thread的信息,是因為它的內部有一個Values內部類,而Values中有一個Object組。

  • Objec數組是以一種近似于map的形式來存儲數據的,其中偶數位存ThreadLocal的弱引用,它的下一位存值。

  • 在尋址的時候,Values采用一種很神奇的方式——斐波拉契散列尋址Values里面的getAfterMiss()方式讓人覺得很奇怪

與synchronized同步機制的比較

  • 首先,它們都是為了解決多線程中相同變量訪問沖突問題。不過,在同步機制中,要通過對象的鎖機制保證同一時間只有一個線程訪問該變量。該變量是線程共享的,使用同步機制要求程序縝密地分析什么時候對該變量讀寫,什么時候需要鎖定某個對象,什么時候釋放對象鎖等復雜的問題,程序設計編寫難度較大,是一種“以時間換空間”的方式。
    而ThreadLocal采用了以“以空間換時間”的方式。

7.接口與抽象類

  • 一個子類只能繼承一個抽象類,但能實現多個接口

  • 抽象類可以有構造方法,接口沒有構造方法

  • 抽象類可以有普通成員變量,接口沒有普通成員變量

  • 抽象類和接口都可有靜態成員變量,抽象類中靜態成員變量訪問類型任意,接口只能public static final(默認)

  • 抽象類可以沒有抽象方法,抽象類可以有普通方法,接口中都是抽象方法

  • 抽象類可以有靜態方法,接口不能有靜態方法

  • 抽象類中的方法可以是public、protected和默認;接口方法只有public

8.Statement接口

8.1

  • Statement是最基本的用法,不傳參,采用字符串拼接,存在注入漏洞

  • PreparedStatement傳入參數化的sql語句,同時檢查合法性,效率高,可以重用,防止sql注入

  • CallableStatement接口擴展PreparedStatement,用來調用存儲過程

  • public interface CallableStatement extends PreparedStatement

  • public interface PreparedStatement extends Statement

  • BatchedStatement用于批量操作數據庫,BatchedStatement不是標準的Statement類

8.2 Statement與PrepareStatement的區別

  • 創建時的區別

Statement statement = conn.createStatement();
PreparedStatement preStatement = conn.prepareStatement(sql);
  • 執行的時候

ResultSet rSet = statement.executeQuery(sql);
ResultSet pSet = preStatement.executeQuery();

由上可以看出,PreparedStatement有預編譯的過程,已經綁定sql,之后無論執行多少遍,都不會再去進行編譯,而 statement 不同,如果執行多遍,則相應的就要編譯多少遍sql,所以從這點看,preStatement 的效率會比 Statement要高一些

  • 安全性

preStatement是預編譯的,所以可以有效的防止SQL注入等問題

  • 代碼的可讀性和可維護性

PreparedStatement更勝一籌

9.抽象類和最終類

抽象類可以沒有抽象方法,最終類可以,沒有最終方法

最終類不能被繼承,最終方法不能被重寫(可以重載)

10.異常

10.1 throw、throws、try...catch、finally

  • throws用在方法上,方法內部通過throw拋出異常

  • try用于檢測包住的語句塊,若有異常,拋出并執行catch子句

  • catch捕獲try塊中拋出的異常并處理

10.2 關于finally

  • finally不管有沒有異常都要處理

  • finally{}比return先執行,多個return執行一個后就不在執行

  • 不管有木有異常拋出,finally在return返回前執行

10.3 受檢查異常和運行時異常

圖片描述

  • 粉紅色的是受檢查的異常(checked exceptions),其必須被try...catch語句塊所捕獲,或者在方法簽名里通過throws子句聲明。受檢查的異常必須在編譯時被捕捉處理,命名為Checked Exception是因為Java編譯器要進行檢查,Java虛擬機也要進行檢查,以確保這個規則得到遵守。

  • 綠色的異常是運行時異常(runtime exceptions),需要程序員自己分析代碼決定是否捕獲和處理,比如空指針,被0除...

  • 而聲明為Error的,則屬于嚴重錯誤,如系統崩潰、虛擬機錯誤、動態鏈接失敗等,這些錯誤無法恢復或者不可能捕捉,將導致應用程序中斷,Error不需要捕捉。

11.this & super

11.1 super出現在父類的子類中。有三種存在方式

  • super.xxx(xxx為變量名或對象名)意思是獲取父類中xxx的變量或引用

  • super.xxx(); (xxx為方法名)意思是直接訪問并調用父類中的方法

  • super() 調用父類構造

  • super只能指代其直接父類

11.2 this() & super()在構造方法中的區別

  • 調用super()必須寫在子類構造方法的第一行,否則編譯不通過

  • super從子類調用父類構造,this在同一類中調用其他構造

  • 均需要放在第一行

  • 盡管可以用this調用一個構造器,卻不能調用2個

  • this和super不能出現在同一個構造器中,否則編譯不通過

  • this()、super()都指的對象,不可以在static環境中使用

  • 本質this指向本對象的指針。super是一個關鍵字

12.修飾符一覽

修飾符 類內部     同一個包        子類      任何地方
private         yes
default         yes         yes
protected       yes         yes yes
public          yes         yes yes         yes

13.構造內部類對象

public class Enclosingone {
    public class Insideone {}
    public static class Insideone{}
}

public class Test {
    public static void main(String[] args) {
    Enclosingone.Insideone obj1 = new Enclosingone().new Insideone();
    Enclosingone.Insideone obj2 = new Enclosingone.Insideone();
    }
}

14.序列化

聲明為static和transient類型的數據不能被序列化,序列化的筆記參見Java-note-序列化.md

15.Java的方法區

與堆一樣,是線程共享的區域。方法區中存儲:被虛擬機加載的類信息,常量,靜態變量,編譯器編譯后的代碼等數據。這個區域的內存回收目標主要是針對常量池的對象的回收和對類型的卸載。

16.正則表達式

次數符號

* 0或多次
+ 1或多次
?0或1次
{n} 恰n次
{n,m} 從n到m次

其他符號

符號 等價形式

\d      [0-9]
\D      [^0-9]  
\w      [a-zA-Z_0-9]
\W      [^a-zA-Z_0-9]
\s      [\t\n\r\f]
\S      [^\t\n\r\f]
.       任何字符

邊界匹配器

行開頭 ^
行結尾 $
單詞邊界 b

貪婪模式:最大長度匹配 非貪婪模式:匹配到結果就好,最短匹配

環視

字符  描述      匹配對象
.       單個任意字符          
[...]   字符組         列出的任意字符
[^...]  未列出的任意字符
^       caret       行的起始位置
$       dollar      行的結束位置
\<      單詞的起始位置
\>      單詞的結束位置
\b      單詞邊界
\B      非單詞邊界
(?=Expression)      順序肯定環視          成功,如果右邊能夠匹配
(?!Expression)      順序否定環視          成功,如果右邊不能夠匹配
(?<=Expression)     逆序肯定環視          成功,如果左邊能夠匹配
(?<!Expression)     逆序否定環視          成功,如果左邊不能夠匹配

舉例:北京市(海定區)(朝陽區)(西城區)

Regex: .*(?=()

模式和匹配器的典型調用次序

  • 把正則表達式編譯到模式中
    Pattern p = Pattern.compile("a*b");

  • 創建給定輸入與此模式的匹配器
    Matcher m = p.matcher("aaab");

  • 嘗試將整個區域與此模式匹配

  1. b = m.matches();

17.Servlet & JSP & Tomcat

17.1 Servlet繼承實現結構

Servlet (接口)-->      init|service|destroy方法
GenericServlet(抽象類)  -->      與協議無關的Servlet
HttpServlet(抽象類)        -->      實現了http協議
自定義Servlet          -->      重寫doGet/doPost

17.2 編寫Servlet的步驟

  • 繼承HttpServlet

  • 重寫doGet/doPost方法

  • 在web.xml中注冊servlet

17.3 Servlet生命周期

  • init:僅執行一次,負責裝載servlet時初始化servlet對象

  • service:核心方法,一般get/post兩種方式

  • destroy:停止并卸載servlet,釋放資源

17.4 過程

  • 客戶端request請求 -> 服務器檢查Servlet實例是否存在 -> 若存在調用相應service方法

  • 客戶端request請求 -> 服務器檢查Servlet實例是否存在 -> 若不存在裝載Servlet類并創建實例 -> 調用init初始化 -> 調用service

  • 加載和實例化、初始化、處理請求、服務結束

17.5 doPost方法要拋出的異常:ServletExcception、IOException

17.6 Servlet容器裝載Servlet

  • web.xml中配置load-on-startup啟動時裝載

  • 客戶首次向Servlet發送請求

  • Servlet類文件被更新后,重新裝載Servlet

17.7 HttpServlet容器響應web客戶請求流程

  • Web客戶向servlet容器發出http請求

  • servlet容器解析Web客戶的http請求

  • servlet容器創建一個HttpRequest對象,封裝http請求信息

  • servlet容器創建一個HttpResponse對象

  • servlet容器調用HttpServlet的service方法,把HttpRequest和HttpResponse對象作為service方法的參數傳給HttpServlet對象

  • HttpServlet調用httprequest的有關方法,獲取http請求信息

  • httpservlet調用httpresponse的有關方法,生成響應數據

  • Servlet容器把HttpServlet的響應結果傳給web客戶

17.8 HttpServletRequest完成的功能

  • request.getCookie()

  • request.getHeader(String s)

  • request.getContextPath()

17.9 HttpServletResponse完成的功能

  • 設http頭

  • 設置Cookie

  • 輸出返回數據

17.10 session

HttpSession session = request.getSession(boolean create)
返回當前請求的會話

17.11 JSP的前身就是Servlet

17.12 Tomcat容器的等級

Tomcat - Container - Engine - Host - Servlet - 多個Context(一個Context對應一個web工程)-Wrapper

17.13 Servlet與JSP九大內置對象的關系

JSP對象 怎樣獲得

1. out  ->      response.getWriter
2. request      ->      Service方法中的req參數
3. response         ->      Service方法中的resp參數
4. session      ->      request.getSession
5. application  ->      getServletContext
6. exception        ->      Throwable
7. page ->      this
8. pageContext      ->      PageContext
9. Config           ->      getServletConfig

exception是JSP九大內置對象之一,其實例代表其他頁面的異常和錯誤。只有當頁面是錯誤處理頁面時,即isErroePage為 true時,該對象才可以使用。

18.struts

  • struts可進行文件上傳

  • struts基于MVC模式

  • struts讓流程結構更清晰

  • struts有許多action類,會增加類文件數目

19.Hibernate的7大鼓勵措施

  • 盡量使用many-to-one,避免使用單項one-to-many

  • 靈活使用單項one-to-many

  • 不用一對一,使用多對一代替一對一

  • 配置對象緩存,不使用集合對象

  • 一對多使用bag,多對一使用set

  • 繼承使用顯示多態

  • 消除大表,使用二級緩存

20.JVM

20.1 JVM內存配置參數

  • -Xmx:最大堆大小

  • -Xms:初始堆大小(最小內存值)

  • -Xmn:年輕代大小

  • -XXSurvivorRatio:3 意思是Eden:Survivor=3:2

  • -Xss棧容量

  • -XX:+PrintGC 輸出GC日志

  • -XX:+PrintGCDetails 輸出GC的詳細日志

20.2 JVM內存結構

  • 堆:Eden、Survivor、old 線程共享

  • 方法區(非堆):持久代,代碼緩存,線程共享

  • JVM棧:中間結果,局部變量,線程隔離

  • 本地棧:本地方法(非Java代碼)

  • 程序計數器 :線程私有,每個線程都有自己獨立的程序計數器,用來指示下一條指令的地址

  • 注:持久代Java8消失,取代的稱為元空間(本地堆內存的一部分)

21.面向對象的五大基本原則(solid)

  • S單一職責SRP:Single-Responsibility Principle
    一個類,最好只做一件事,只有一個引起它的變化。單一職責原則可以看做是低耦合,高內聚在面向對象原則的引申,將職責定義為引起變化的原因,以提高內聚性減少引起變化的原因。

  • O開放封閉原則OCP:Open-Closed Principle
    軟件實體應該是可擴展的,而不是可修改的。對擴展開放,對修改封閉

  • L里氏替換原則LSP:Liskov-Substitution Principle
    子類必須能夠替換其基類。這一思想表現為對繼承機制的約束規范,只有子類能夠替換其基類時,才能夠保證系統在運行期內識別子類,這是保證繼承復用的基礎。

  • I接口隔離原則ISP:Interface-Segregation Principle
    使用多個小的接口,而不是一個大的總接口

  • D依賴倒置原則DIP:Dependency-Inversion Principle
    依賴于抽象。具體而言就是高層??椴灰覽滌詰撞隳??二者共同依賴于抽象。抽象不依賴于具體,具體依賴于抽象。

面向對象設計原則

  • 封裝變化

  • 少用繼承 多用組合

  • 針對接口編程 不針對實現編程

  • 為交互對象之間的松耦合設計而努力

  • 類應該對擴展開發 對修改封閉(開閉OCP原則)

  • 依賴抽象,不要依賴于具體類(依賴倒置DIP原則)

  • 密友原則:只和朋友交談(最少知識原則)

說明:將方法調用保持在界限內,只調用屬于以下范圍的方法:
該對象本身(本地方法)對象的組件 被當作方法參數傳進來的對象 此方法創建或實例化的任何對象

  • 別找我(調用我) 我會找你(調用你)(好萊塢原則)

  • 一個類只有一個引起它變化的原因(單一職責SRP原則)

22.null可以被強制轉型為任意類型的對象。

23.代碼執行次序

  • 多個靜態成員變量,靜態代碼塊按順序執行

  • 單個類中: 靜態代碼 -> main方法 -> 構造塊 -> 構造方法

  • 構造塊在每一次創建對象時執行

  • 涉及父類和子類的初始化過程
    a.初始化父類中的靜態成員變量和靜態代碼塊

b.初始化子類中的靜態成員變量和靜態代碼塊
c.初始化父類的普通成員變量和構造代碼塊(按次序),再執行父類的構造方法(注意父類構造方法中的子類方法覆蓋)
d.初始化子類的普通成員變量和構造代碼塊(按次序),再執行子類的構造方法

24.紅黑樹

二叉搜索樹:(Binary Search Tree又名:二叉查找樹,二叉排序樹)它或者是一棵空樹,或者是具有下列性質的二叉樹: 若它的左子樹不空,則左子樹上所有結點的值均小于它的根結點的值;若它的右子樹不空,則右子樹上所有結點的值均大于它的根結點的值;它的左、右子樹也分別為二叉搜索樹。

紅黑樹的定義:滿足以下五個性質的二叉搜索樹

  • 每個結點或是紅色的或是黑色的

  • 根結點是黑色的

  • 每個葉結點是黑色的

  • 如果一個結點是紅色的,則它的兩個子結點是黑色的

  • 對于每個結點,從該結點到其后代葉結點的簡單路徑上,均包含相同數目的黑色結點

黑高

從某個結點x出發(不含x)到達一個葉結點的任意一條簡單路徑上的黑色結點個數稱為該結點的黑高。
紅黑樹的黑高為其根結點的黑高。

其他

  • 一個具有n個內部結點的紅黑樹的高度h<=2lg(n+1)

  • 結點的屬性(五元組):color key left right p

  • 動態集合操作最壞時間復雜度為O(lgn)

25.排序

  • 穩定排序:插入排序、冒泡排序、歸并排序、基數排序

  • 插入排序[穩定]
    適用于小數組,數組已排好序或接近于排好序速度將會非???/p>

復雜度:O(n^2) - O(n) - O(n^2) - O(1)[平均 - 最好 - 最壞 - 空間復雜度]

  • 歸并排序[穩定]
    采用分治法

復雜度:O(nlogn) - O(nlgn) - O(nlgn) - O(n)[平均 - 最好 - 最壞 - 空間復雜度]

  • 冒泡排序[穩定]
    復雜度:O(n^2) - O(n) - O(n^2) - O(1)[平均 - 最好 - 最壞 - 空間復雜度]

  • 基數排序 分配+收集[穩定]
    復雜度: O(d(n+r)) r為基數d為位數 空間復雜度O(n+r)

  • 樹排序
    應用:TreeSet的add方法、TreeMap的put方法

不支持相同元素,沒有穩定性問題
復雜度:平均最差O(nlogn)

  • 堆排序(就地排序)
    復雜度:O(nlogn) - O(nlgn) - O(nlgn) - O(1)[平均 - 最好 - 最壞 - 空間復雜度]

  • 快速排序
    復雜度:O(nlgn) - O(nlgn) - O(n^2) - O(1)[平均 - 最好 - 最壞 - 空間復雜度]

棧空間0(lgn) - O(n)

  • 選擇排序
    復雜度:O(n^2) - O(n^2) - O(n^2) - O(1)[平均 - 最好 - 最壞 - 空間復雜度]

  • 希爾排序
    復雜度 小于O(n^2) 平均 O(nlgn) 最差O(n^s)[1<s<2] 空間O(1)

26.查找與散列

26.1 散列函數設計

  • 直接定址法:f(key) = a*key+b

簡單、均勻,不易產生沖突。但需事先知道關鍵字的分布情況,適合查找表較小且連續的情況,故現實中并不常用

  • 除留余數法:f(key) = key mod p (p<=m) p取小于表長的最大質數 m為表長

  • DJBX33A算法(time33哈希算法hash = hash*33+(unsigned int)str[i];

平方取中法 折疊法 更多....

26.2 沖突處理

閉散列(開放地址方法):要求裝填因子a較小,閉散列方法把所有記錄直接存儲在散列表中

  • 線性探測:易產生堆積現象(基地址不同堆積在一起)

  • 二次探測:f(key) = (f(key)+di) % m di=1

  • 隨機探測:f(key) = (f(key)+di),di采用隨機函數得到,可以消除基本聚集

  • 雙散列:避免二次聚集

開散列(鏈地址法):原地處理

  • 同義詞記錄存儲在一個單鏈表中,散列表中子存儲單鏈表的頭指針。

  • 優點:無堆積 事先無需確定表長 刪除結點易于實現 裝載因子a>=1,缺點:需要額外空間

27.枚舉類

JDK1.5出現 每個枚舉值都需要調用一次構造函數

28.數組復制方法

  • for逐一復制

  • System.arraycopy() -> 效率最高native方法

  • Arrays.arrayOf() -> 本質調用arraycopy

  • clone方法 -> 返回Object[],需要強制類型轉換

29.多態

  • Java通過方法重寫和方法重載實現多態

  • 方法重寫是指子類重寫了父類的同名方法

  • 方法重載是指在同一個類中,方法的名字相同,但是參數列表不同

30.Java文件

.java文件可以包含多個類,唯一的限制就是:一個文件中只能有一個public類, 并且此public類必須與
文件名相同。而且這些類和寫在多個文件中沒有區別。

31.Java移位運算符

java中有三種移位運算符

1.<< :左移運算符,x << 1,相當于x乘以2(不溢出的情況下),低位補0

2.帶符號右移,x >> 1,相當于x除以2,正數高位補0,負數高位補1

3.無符號右移,忽略符號位,空位都以0補齊

32.形參&實參

  • 形式參數可被視為local variable.形參和局部變量一樣都不能離開方法。只有在方法中使用,不會在方法外可見。

  • 形式參數只能用final修飾符,其它任何修飾符都會引起編譯器錯誤。但是用這個修飾符也有一定的限制,就是在方法中不能對參數做任何修改。不過一般情況下,一個方法的形參不用final修飾。只有在特殊情況下,那就是:方法內部類。一個方法內的內部類如果使用了這個方法的參數或者局部變量的話,這個參數或局部變量應該是final。

  • 形參的值在調用時根據調用者更改,實參則用自身的值更改形參的值(指針、引用皆在此列),也就是說真正被傳遞的是實參。

33.IO

圖片描述

34.局部變量為什么要初始化

局部變量是指類方法中的變量,必須初始化。局部變量運行時被分配在棧中,量大,生命周期短,如果虛擬機給每個局部變量都初始化一下,是一筆很大的開銷,但變量不初始化為默認值就使用是不安全的。出于速度和安全性兩個方面的綜合考慮,解決方案就是虛擬機不初始化,但要求編寫者一定要在使用前給變量賦值。

35.JDK提供的用于并發編程的同步器

  • Semaphore Java并發庫的Semaphore可以很輕松完成信號量控制,Semaphore可以控制某個資源可被同時訪問的個數,通過 acquire() 獲取一個許可,如果沒有就等待,而 release() 釋放一個許可。

  • CyclicBarrier 主要的方法就是一個:await()。await()方法每被調用一次,計數便會減少1,并阻塞住當前線程。當計數減至0時,阻塞解除,所有在此CyclicBarrier上面阻塞的線程開始運行。

  • 直譯過來就是倒計數(CountDown)門閂(Latch)。倒計數不用說,門閂的意思顧名思義就是阻止前進。在這里就是指 CountDownLatch.await() 方法在倒計數為0之前會阻塞當前線程。

36.Java類加載器

一個jvm中默認的classloader有Bootstrap ClassLoader、Extension ClassLoader、App ClassLoader,分別各司其職:

  • Bootstrap ClassLoader(引導類加載器) 負責加載java基礎類,主要是 %JRE_HOME/lib/目錄下的rt.jar、resources.jar、charsets.jar等

  • Extension ClassLoader(擴展類加載器) 負責加載java擴展類,主要是 %JRE_HOME/lib/ext目錄下的jar等

  • App ClassLoader(系統類加載器) 負責加載當前java應用的classpath中的所有類。

  1. 加載類用的是全盤負責委托機制。 所謂全盤負責,即是當一個classloader加載一個Class的時候,這個Class所依賴的和引用的所有 Class也由這個classloader負責載入,除非是顯式的使用另外一個classloader載入。

所以,當我們自定義的classloader加載成功了com.company.MyClass以后,MyClass里所有依賴的class都由這個classLoader來加載完成。

37.Java語言的魯棒性

Java在編譯和運行程序時,都要對可能出現的問題進行檢查,以消除錯誤的產生。它提供自動垃圾收集來進行內存管理,防止程序員在管理內存時容易產生的錯誤。通過集成的面向對象的例外處理機制,在編譯時,Java揭示出可能出現但未被處理的例外,幫助程序員正確地進行選擇以防止系統的崩潰。另外,Java在編譯時還可捕獲類型聲明中的許多常見錯誤,防止動態運行時不匹配問題的出現。

38.Java語言特性

  • Java致力于檢查程序在編譯和運行時的錯誤

  • Java虛擬機實現了跨平臺接口

  • 類型檢查幫助檢查出許多開發早期出現的錯誤

  • Java自己操縱內存減少了內存出錯的可能性

  • Java還實現了真數組,避免了覆蓋數據的可能

39.Hibernate延遲加載

  • Hibernate2延遲加載實現:a)實體對象 b)集合(Collection)

  • Hibernate3 提供了屬性的延遲加載功能
    當Hibernate在查詢數據的時候,數據并沒有存在與內存中,當程序真正對數據的操作時,對象才存在與內存中,就實現了延遲加載,他節省了服務器的內存開銷,從而提高了服務器的性能。

  • hibernate使用Java反射機制,而不是字節碼增強程序來實現透明性。

  • hibernate的性能非常好,因為它是個輕量級框架。映射的靈活性很出色。它支持各種關系數據庫,從一對一到多對多的各種復雜關系。

40.包裝類的equals()方法不處理數據轉型,必須類型和值都一樣才相等。

41.子類可以繼承父類的靜態方法!但是不能覆蓋。因為靜態方法是在編譯時確定了,不能多態,也就是不能運行時綁定。

42.Java語法糖

  • Java7的switch用字符串 - hashcode方法 switch用于enum枚舉

  • 偽泛型 - List< E>原始類型

  • 自動裝箱拆箱 - Integer.valueOf和Integer.intValue

  • foreach遍歷 - Iterator迭代器實現

  • 條件編譯

  • enum枚舉類、內部類

  • 可變參數 - 數組

  • 斷言語言

  • try語句中定義和關閉資源

43.JVM工具

命令行

  • jps(jvm processor status)虛擬機進程狀況工具

  • jstat(jvm statistics monitoring)統計信息監視

  • jinfo(configuration info for java)配置信息工具

  • jmap(memory map for java)Java內存映射工具

  • jhat(JVM Heap Analysis Tool)虛擬機堆轉儲快照分析工具

  • jstack(Stack Trace for Java)Java堆棧跟蹤工具

  • HSDIS:JIT生成代碼反匯編

可視化

  • JConsole(Java Monitoring and Management Console):Java監視與管理控制臺

  • VisualVM(All-in-one Java Troubleshooting Tool):多合一故障處理工具

44.內部類為什么可以訪問外部類的私有屬性

在內部類構造的時候,會將外部類的引用傳遞進來,并且作為內部類的一個屬性,所以內部類會持有一個其外部類的引用。

當內部類調用外部類的私有屬性時,其真正的執行是調用了編譯器生成的屬性的靜態方法(即acess1等)來獲取這些屬性值。這一切都是編譯器的特殊處理。

外部類可以通過內部類的實例獲取私有屬性x的操作.

45.如何讓內部類私有成員不被外部訪問

使用匿名內部類

public class PrivateToOuter {
  Runnable mRunnable = new Runnable(){
      private int x=10;
      @Override
      public void run() {
          System.out.println(x);
      }
  };

  public static void main(String[] args){
      PrivateToOuter p = new PrivateToOuter();
      //System.out.println("anonymous class private filed= "+ p.mRunnable.x); //not allowed
      p.mRunnable.run(); // allowed
  }
}

由于mRunnable對象的類型為Runnable,而不是匿名內部類的類型(我們無法正常拿到),而Runanble中沒有x這個屬性,所以mRunnable.x是不被允許的。

46. Java匿名內部類訪問外部變量,為何需被標志為final?

  • 這要從閉包說起,匿名內部類和外部方法形成了一個閉包,因此,匿名內部類能夠訪問外部方法的變量,看起來是一種“天經地義”的事情,Java語言當然也需要實現這種特性,但是這里遇到了一個問題。

  • 匿名內部類的生命周期可能比外部的類要長,因此訪問外部局部變量有可能是訪問不到的。

  • 那怎么辦呢?Java語言為了實現這種特性, 只好將外部的局部變量偷偷的賦值了一份給匿名內部類。那這樣匿名內部類就可以肆無忌憚的訪問外部局部變量了。

  • 問題又來了,這種通過賦值的形式有一個缺陷,匿名內部類不可以修改“原來的局部變量”,因為是一份“復制品”,修改復制品對原變量沒什么影響啊。

  • 那怎么辦? Java語言干脆強制要求被匿名內部類訪問的外部局部變量必須是final的,什么意思呢?就是“一刀切”,不讓修改了。

47. 非靜態內部類為什么不能有靜態成員

  • static類型的屬性和方法,在類加載的時候就會存在于內存中。

  • 要想使用某個類的static屬性和方法,那么這個類必須要加載到虛擬機- 中。

  • 非靜態內部類并不隨外部類一起加載,只有在實例化外部類之后才會加載。

在外部類并沒有實例化,內部類還沒有加載,這時候如果調用內部類的靜態成員或方法,內部類還沒有加載,卻試圖在內存中創建該內部類的靜態成員,這明顯是矛盾的。

所以非靜態內部類不能有靜態成員變量或靜態方法。

48. 手寫實現二分查找

    /**
 * 使用遞歸的二分查找
 **title:recursionBinarySearch
 **@param arr 有序數組
 **@param key 待查找關鍵字
 **@return 找到的位置
 */
public static int recursionBinarySearch( int[] arr, int key, int low, int high )
{
    if ( key < arr[low] || key > arr[high] || low > high )
    {
        return(-1);
    }

    int middle = (low + high) / 2; /* 初始中間位置 */
    if ( arr[middle] > key )
    {
        /* 比關鍵字大則關鍵字在左區域 */
        return(recursionBinarySearch( arr, key, low, middle - 1 ) );
    }else if ( arr[middle] < key )
    {
        /* 比關鍵字小則關鍵字在右區域 */
        return(recursionBinarySearch( arr, key, middle + 1, high ) );
    }else {
        return(middle);
    }
}

作者:hackest
出自:https://www.jianshu.com/p/26ccd6b1b71c


我來說兩句
您需要登錄后才可以評論 登錄 | 立即注冊
facelist
所有評論(1)
雨漸漸 2019-5-24 18:04
漲姿勢了,我要記錄在安卓手機、蘋果手機、電腦以及iPad通用的敬業簽云便簽上,需要的時候時時查看。
回復
領先的中文移動開發者社區
18620764416
7*24全天服務
意見反?。[email protected]

掃一掃關注我們

Powered by Discuz! X3.2© 2001-2019 Comsenz Inc.( 致富之地一肖中特 )