最近閑的很，想和大家一起學習并討論下Java的一些源代碼以及其實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，

不是什么高水平的東西，有興趣的隨便看看

1. 為什么要用Map，以HashMap為例

很多時候我們有這樣的需求，我們需要將數(shù)據(jù)成鍵值對的方式存儲起來，根據(jù)key來獲取value(value可以是簡單值，也可以是自定義對象)

當然用對象數(shù)組也能實現(xiàn)這個目的，查找時可以遍歷數(shù)組，比較關(guān)鍵字來獲取對應的value

從性能上來講，遍歷大數(shù)組會消耗性能

從API易用性來講，需要自己實現(xiàn)查找的邏輯

所以用HashMap是必要的

2. HashMap的數(shù)據(jù)結(jié)構(gòu)是怎么樣的

我一直對HashMap的內(nèi)部結(jié)構(gòu)很好奇，看了源碼之后發(fā)現(xiàn)他是用散列實現(xiàn)的，即基于hashcode

大體思想是這樣的

2.1 首先建立一個數(shù)組用來存取數(shù)據(jù)，假設我們定義一個Object[] table用來存取map的value

這個很容易理解，key存在哪里呢？暫時我不想存儲key

2.2 獲得key的hashcode經(jīng)過一定算法轉(zhuǎn)成一個整數(shù)

index，這個index的取值范圍必須是0=<index<table.length，然后我將其作為數(shù)組元素的下標

比如執(zhí)行這樣的操作：table[index] = value;

這樣存儲的問題解決了

2.3 如何通過key去獲取這個value呢

這個太簡單了，首先獲取key的hashcode，然后通過剛才一樣的算法得出元素下標index

然后value = table[index]

簡單的HashTable實現(xiàn)如下

public class SimpleHashMap {    PRivate Object[] table;    public SimpleHashMap() {        table = new Object[10];    }    public Object get(Object key) {        int index = indexFor(hash(key.hashCode()), 10);        return table[index];    }    public void put(Object key, Object value) {        int index = indexFor(hash(key.hashCode()), 10);        table[index] = value;    }    /**     * 通過hash code 和table的length得到對應的數(shù)組下標     *      * @param h     * @param length     * @return     */    static int indexFor(int h, int length) {        return h & (length - 1);    }    /**     * 通過一定算法計算出新的hash值     *      * @param h     * @return     */    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }            public static void main(String[] args){        SimpleHashMap hashMap = new SimpleHashMap();        hashMap.put("key", "value");        System.out.println(hashMap.get("key"));    }}

這個簡單的例子大概描述了散列實現(xiàn)hashmap的過程

但是還很不成熟，我發(fā)現(xiàn)至少存在以下兩個問題

1. hashmap的size是固定的

2. 如果不同的key通過hashcode得出的index相同呢，這樣的情況是存在的，如何解決？

請看系列文章二