OpenJDK 源碼閱讀之 Arrays

類繼承關系

定義

要點

此類主要是提供了一些操作數組的方法，比如排序啊，搜尋啊。也提供一個工廠，用于将數組當成一個 <code>List</code>。

quick sort

<code>sort</code> 使用了 <code>util</code> 中的另一個類中的方法，<code>DualPivotQuicksort.sort</code> ，比一般的快排要快。時間複雜度 <code>O(n log(n))</code>。

這裡并沒有使用泛型，而是針對具體類型，調用 <code>sort</code>，例如：

<code>DualPivotQuicksort</code> 的實作細節會在以後具體講述這個類的源代碼時講。現在隻講這個類中的内容。

merge sort

當數組元素個數少時，用插入排序，插入排序的原理是，在一個已經排序的清單中插入一個元素，使得插入後，清單仍然是排序的。具體到代碼，每一次，内層循環開始前，[low,i-1] 的所有元素是已經排序的，内層循環執行後，[low, i] 的所有元素是已經排序的。i最終會等于 high-1，所有最後一層内層循環後，[low, high-1]中所有元素都是已經排序的。

合并排序 <code>merge sort</code> 的原理是，通過遞歸，先使得前一半元素，和後一半元素使用合并排序排好，然後将他們合并，合并後，整個清單是有序的。合并時，兩部分元素上面各有一個指針指向目前元素，每次将兩個指針指向的元素進行比較，并選擇其中一個，複制到目标數組，然後将其指針前移。如此循環。

注意代碼中有一個優化，如果兩半元素排序後，前一半的最大元素小于後一半的最小元素，那麼不用比較，直接合并。

不過這個函數已經要廢棄了，現在用的是 <code>sort</code> ，即使用快排。

TimSort

對提供了 <code>Comparator</code> 的排序調用，這裡使用了 <code>TimSort</code>，根據注釋中的解釋，這是采用 <code>Tim Peters</code> 在 <code>Python</code> 的 <code>list</code> 中的排序，原始論文參見：<code>Peter McIlroy‘s "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993</code>。這個算法對已經大緻排好序的清單，花費的時間比 <code>O(n log(n))</code> 少很多，對随機的資料，退化為 <code>merge sort</code>。

binarySearch

對已經排序的元素，可以使用二分搜尋，一次可以排除一半元素，複雜度 <code>O(log(n))</code>。

可以注意到，這也是針對具體類型編寫的。如果使用泛型，那麼需要告訴算法如何比較元素。這樣，基本類型就需要使用對應的類來表示，而對數組而言，基本類型無法自動轉化成對應的類。真是。。。哎。。。。Java 為什麼要保留基本類型呢？

equals

周遊比較，毫無疑問，又是每種類型，一個函數。保留基本類型真是正确的選擇嗎？

fill

使用一個元素，去填充數組的所有元素。

copyOf

使用 <code>System.arraycopy</code> 複制，友善，省心，不自己循環！

asList

就是直接生成一個 <code>ArrayList</code>，隻不過這個 <code>ArrayList</code> 是 <code>Arrays</code> 中的私有類。

ArrayList

因為之前分析過 <code>ArrayList</code> ，這個是個針對數組的簡單版本，就不具體分析了。

hashCode

又看到了常見的 <code>hashcode</code> 模式：

不過那個 <code>element ^ (element &gt;&gt;&gt; 32)</code> 是嘛意思，注意這裡的 <code>element</code> 是 <code>long</code> 類型，64位，這裡是将高

32 位與低 32 位作了 <code>^</code> 運算，再轉型成 <code>int</code> 。這是因為 <code>hashCode</code> 是

32 位的。再看看 <code>int</code> 數組的 <code>hashCode</code> 就正常多了。

另外， <code>boolean</code> 類型的數組猜一猜 <code>hashCode</code> 如何确定？

這是将 <code>true</code> 和 <code>false</code> 變成了兩個數字，<code>1231</code>, <code>1237</code>。為什麼要換成這兩個數字呢？還不太清楚，不過總的原因就是減少碰撞，看來有必要研究一下哈希函數的設計了。

deepXXX

先看看 <code>deepHashCode</code>:

這是需要根據 <code>Object</code> 數組中的每一個的具體類型，來決定目前元素的哈希值。

同理，可以看看 <code>deepEquals</code>:

同樣需要根據類型來比較每個元素是否相等。

toString

同樣，每個基本類型都有相應的函數，使用 <code>StringBuilder</code>，具體如何将 <code>long</code> 轉化成 <code>String</code> ，由 <code>StringBuilder</code> 來确定。