看完上一個章節，相信你已經充分的掌握了資料庫事務的一些事情，猿人工廠君也知道，内容對于新手而言，了解起來還是比較很吃力的，文中提到的原理和内容，有興趣的可以和我一起探讨，猿人工廠君就不一一贅述了。之前有小夥伴反應，資料結構的知識比較薄弱，今天我們就來探讨下，通過思考的方式，來解決基本的資料結構問題。本文是思考系列的最後一章，從下一章節開始，帶你玩兒架構和實戰完成猿蛻變！
相信大家都使用過無數次ArrayList了，一個大家常用的集合容器——可變數組。既然是容器，那自然是什麼東西都能存放的啦。數組一般來說都是長度不變的，那要做到長度可變該怎麼辦呢？
開動你的小腦筋，既然要存放任何資料，那自然是Object比較可靠啦，對象之祖，可以表示仍和資料。長度可變，自然是存放滿了之後，改變數組長度了。
嗯，在數組種放入資料确實簡單，但是依然是有一些隐藏邏輯的。想想看，比如數組越界的處理，比如增加或删除資料後，原有資料發生移動，比如資料存放時，恰巧遇到資料滿了之後，原有資料需要拷貝和移動。以上這些都是數組操作的隐藏邏輯噢，發現這些隐藏邏輯，對你的編碼能力和業務分析能力的提升是很有幫助的。下面是一個簡單的實作，拿走不謝噢。
package com.pz.collection.demo;
/**
* pangzi
* 模拟實作ArrayList
*/
public class ArrayList {
//使用數組存放資料
privateO bject[] elementData;
//數組大小
private int size;
/**
*無參構造方法 預設大小10
*/
public ArrayList(){
this(10);
}
/**
*
* @paraminitialCapacity
*/
public ArrayList(int initialCapacity){
if(initialCapacity<0){
try {
throw new Exception();
}catch (Exception e) {
e.printStackTrace();
}
}
elementData=new Object[initialCapacity];
}
/**
* 判斷容器是否為空
* @return
*/
public boolean isEmpty(){
return size==0;
}
/**
* 根據下标擷取元素
* @paramindex
* @return
*/
public Object get(int index){
rangeCheck(index);
return elementData[index];
}
/**
* 預設增加在數組尾部增加元素
* @paramobj
* @return
*/
public boolean add(Object obj){
ensureCapacity();
elementData[size]=obj;
size++;
return true;
}
/**
* 在指定下标增加元素
* @paramindex
* @paramobj
*/
public void add(int index,Object obj){
rangeCheck(index);
ensureCapacity();
System.arraycopy(elementData, index, elementData, index+1,size-index);
elementData[index]=obj;
size++;
}
/**
* 删除指定下标元素
* @param index
* @return
*/
public Object remove(int index){
rangeCheck(index);
int arrnums=size-index-1;
ObjectoldValue=elementData[index];
if(arrnums>0){
System.arraycopy(elementData, index+1, elementData,index, arrnums);
}
elementData[--size]=null;
return oldValue;
}
/**
* 根據對象删除元素
* @paramobj
* @return
*/
public boolean remove(Object obj){
for(int i=0;i<size;i++){
if(get(i).equals(obj)){
remove(i);
}
break;
}
return true;
}
/**
* 根據下标改變對象并傳回舊的值
*
* @paramindex 下标
* @paramobj 元素
* @return
*/
public Object set(int index,Object obj){
rangeCheck(index);
ObjectoldValue=elementData[index];
elementData[index]=obj;
return oldValue;
}
/**
* 範圍檢查
* @paramindex 下标
*/
private void rangeCheck(int index){
if(index<0||index>=size){
try {
throw new Exception();
}catch (Exception e) {
e.printStackTrace();
}
}
}
/**
* 數組擴容檢查
*/
private void ensureCapacity(){
if(size==elementData.length){
Object[] newArray=new Object[size*2+1];
System.arraycopy(elementData, 0, newArray, 0, elementData.length);
elementData=newArray;
}
}
/**
* 傳回元素第一次出現下标
* 如果無元素傳回-1
* @paramobj
* @return
*/
public int indexOf(Object obj) {
if(obj == null) {
for (int i = 0; i < size; i++){
if (elementData[i]==null){
return i;
}
}
} else{
for (int i = 0; i < size; i++){
if (obj.equals(elementData[i])){
return i;
}
}
}
return-1;
}
/**
* 傳回元素最後一次出現下标
* 如果無元素傳回-1
* @paramobj
* @return
*/
public int lastIndexOf(Object obj) {
if(obj != null) {
for (int i = size-1; i >= 0; i--) {
if (obj.equals(elementData[i])) {
return i;
}
}
} else{
for (int i = size-1; i >= 0; i--) {
if (elementData[i] == null) {
return i;
}
}
}
return-1;
}
/**
* 傳回List大小
* @return
*/
public intsize(){
return size;
}
} 複制
數組的實作已經學會了，那麼數組有什麼特點呢？自然是連續存儲，查找效率較高，但是插入和删除因為發生資料移動的關系，效率會低一些，記住了。面試官經常問的噢。
連結清單是一種實體存儲單元上非連續、非順序的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連結次序實作的。連結清單由一系列結點（連結清單中每一個元素稱為結點）組成，結點可以在運作時動态生成。每個結點包括兩個部分：一個是存儲資料元素的資料域，另一個是存儲下一個結點位址的指針域。。
學會了解概念也是一種本事呢。指針，在java裡是不存在的，但是有一個替代品——引用類型。那怎樣去實作一個連結清單呢？自然是定義一個類，一個Object類型的屬性，用于存放資料，一個next屬性，引用自身，指向下一條資料就好了。這樣一條資料，指向下一條資料的結構，不就像自行車鍊條一樣嗎？如果我們要做插入操作，找到需要插入的位置，改變引用的位置，插入位置的下一個節點，指向新資料，新資料的下一個節點，指向老資料的下一個節點就好了，資料不需要發生移動。删除也是一樣的，找到需要删除的節點，讓被删除的節點的上一個節點，指向被删除的節點的下一個節點就好了。下面是以一個簡單的單向連結清單實作，你可以參考，也可以另行實作。
package com.pz.collection.demo;
/**
* 節點
* pangzi
*/
public class Node{
public Object data;//元素
public Node next;//指針
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
public Node(){
this(null,null);
}
public Node(Object data){
this(data,null);
}
@Override
public String toString() {
return"Node [data=" + data + "]";
}
} 複制
package com.pz.collection.demo;
/**
* 單連結清單
*/
public class LinkedList {
private Node headNode;
private int size;
public LinkedList(){
headNode = new Node(null,null);
size =0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
public void addFirst(Object obj){
add(0,obj);
}
public void addLast(Object obj){
add(size,obj);
}
public void add(int index,Object obj){
if(index < 0 || index > size){
throw new IllegalArgumentException("索引越界異常");
}
Nodeprev = headNode;
for(int i = 0 ; i < index ; i++){
prev = prev.next;
}
prev.next = new Node(obj,prev.next);
size++;
}
public Object get(int index){
if(index < 0 || index > size){
throw newIllegalArgumentException("索引越界異常");
}
Nodecur = headNode.next;
for(int i = 0 ; i < index ; i++){
cur = cur.next;
}
return cur.data;
}
public Object getFirst(){
return get(0);
}
public Object getLast(){
return get(size-1);
}
public void update(int index,Object obj){
if(index < 0 || index > size){
throw new IllegalArgumentException("索引越界異常");
}
Nodecur = headNode.next;
for(int i = 0 ; i < index ; i++){
cur = cur.next;
}
cur.data = obj;
}
public boolean contains(Object obj){
Nodenode = headNode.next;
while(node != null){
if(node.data.equals(obj)){
return true;
}
node = node.next;
}
return false;
}
public void delete(int index){
if(index < 0 || index > size){
throw new IllegalArgumentException("索引越界異常");
}
Nodeprev = headNode;
for(int i = 0 ; i < index ; i++){
prev = prev.next;
}
Nodecur = prev.next;
prev.next = cur.next;
cur.next = null;
size--;
}
public void deleteFirst(){
delete(0);
}
public void deleteLast(){
delete(size-1);
}
public void deleteElement(Object obj){
Nodeprev = headNode;
while(prev.next != null){
if(prev.next.data.equals(obj))
break;
prev = prev.next;
}
if(prev.next != null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size --;
}
}
} 複制
相信你已經看出來了，上面的結構就是HashMap。其實最基本的資料結構從來就隻有兩種：連續存儲的數組和非連續存儲的單連結清單。其餘所有的資料結構，都來自二者的組合。
HashMap就是這樣的一個結構，一個數組，用于存放Entry，Entry通過key進行hash算法快速的定位下标，如果出現hash沖突，那麼将發生沖突的節點，挂到相同hash值的Entry的後面即可。這樣一來，查詢找節點時通過key，進行hash計算，快速定位出元素數組裡的下标，如果沒有立刻找到，再周遊對應的連結清單就好了，插入和删除，都不需要移動元素。算法的好壞關鍵，就在于hash沖突的多少，越少的沖突，帶來越好的性能。
下面就是一個HashMap的簡單實作，你也可以嘗試自己寫一下。
package com.pz.collection.demo;
public class HashMap<K, V> {
private int capacity = 16;
private int size = 0;
private Entry[] table;
public HashMap(int capacity) {
this.capacity = capacity;
this.table = new Entry[capacity];
}
public HashMap() {
this.table = new Entry[capacity];
}
public V put(K key, V value) {
if(key == null) {
return putNullKey(value);
}
inthash = hash(key);
int i= indexTable(hash, capacity);
for(Entry<K, V> e = table[i]; e != null; e = e.next) {
if(e.hash == hash && (e.key == key || e.key.equals(key))) {
V old = e.value;
e.value = value;
return old;
}
}
addEntry(hash, key, value, i);
returnnull;
}
public V get(K key) {
if(key == null)
return getNullKey();
inthash = hash(key);
int i= indexTable(hash, capacity);
for(Entry<K, V> e = table[i]; e != null; e = e.next) {
if(e.hash == hash && (e.key == key || e.key.equals(key)))
return e.value;
}
return null;
}
private V getNullKey() {
for(Entry<K, V> e = table[0]; e != null; e = e.next) {
if(e.key == null)
return e.value;
}
return null;
}
private void addEntry(int hash, K key, V value, int i) {
Entry<K, V> e = table[i];
table[i] = new Entry<K, V>(hash, key, value, e);
if(size == capacity)
resize();
size++;
}
private void resize() {
capacity = capacity * 2;
Entry[] newtable = new Entry[capacity];
for(Entry<K, V> entry : table) {
Entry<K, V> e = entry; // 取得舊Entry數組的每個元素
if(e != null) {
entry = null;// 釋放舊Entry數組的對象引用（循環後，舊的Entry數組不再引用任何對象）
do {
Entry<K, V> next = e.next;
int i = indexTable(e.hash, capacity); // 重新計算每個元素在數組中的位置
e.next = newtable[i];
newtable[i] = e; // 将元素放在數組上
e = next; // 通路下一個Entry鍊上的元素
} while (e != null);
}
}
table= newtable;
}
private int indexTable(int hash, int capacity) {
returnhash & (capacity - 1);
}
private int hash(K key) {
if(key == null)
return 0;
int h= key.hashCode();
h = h^ (h >>> 16);
returnh;
}
private V putNullKey(V value) {
for(Entry<K, V> e = table[0]; e != null; e = e.next) {
if(e.key == null) {
V old = e.value;
e.value = value;
return old;
}
}
addEntry(0, null, value, 0);
return null;
}
}
class Entry<K, V> {
public int hash;
public K key;
public V value;
public Entry<K, V> next;
public Entry(int hash, K key, V value, Entry<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
} 複制