Hash表怎么實(shí)現(xiàn)

本篇內(nèi)容介紹了“Hash表怎么實(shí)現(xiàn)”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

1、什么是Hash表

Hash，一般翻譯做“散列”，也有直接音譯為“哈?！钡?，它是基于快速存取的角度設(shè)計(jì)的，也是一種典型的“空間換時(shí)間”的做法。顧名思義，該數(shù)據(jù)結(jié)構(gòu)可以理解為一個(gè)線(xiàn)性表，但是其中的元素不是緊密排列的，而是可能存在空隙。

 散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。比如我們存儲(chǔ)70個(gè)元素，但我們可能為這70個(gè)元素申請(qǐng)了100個(gè)元素的空間。70/100=0.7，這個(gè)數(shù)字稱(chēng)為負(fù)載(加載)因子。我們之所以這樣做，也 是為了“快速存取”的目的。我們基于一種結(jié)果盡可能隨機(jī)平均分布的固定函數(shù)H為每個(gè)元素安排存儲(chǔ)位置，以達(dá)到快速存取。但是由于此隨機(jī)性，也必然導(dǎo)致一個(gè)問(wèn)題就是沖突。所謂沖突，即兩個(gè)元素通過(guò)散列函數(shù)H得到的地址相同，那么這兩個(gè)元素稱(chēng)為“同義詞”。這類(lèi)似于70個(gè)人去一個(gè)有100個(gè)椅子的飯店吃飯。散列函數(shù)的計(jì)算結(jié)果是一個(gè)存儲(chǔ)單位地址，每個(gè)存儲(chǔ)單位稱(chēng)為“桶”。設(shè)一個(gè)散列表有m個(gè)桶，則散列函數(shù)的值域應(yīng)為[0,m-1]。  

　　這些元素是按照什么樣的規(guī)則存儲(chǔ)到數(shù)組中呢。一般情況是通過(guò)hash(key)%len獲得，也就是元素的key的哈希值對(duì)數(shù)組長(zhǎng)度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲(chǔ)在數(shù)組下標(biāo)為12的位置

2.hash表擴(kuò)容的理解

可是當(dāng)哈希表接近裝滿(mǎn)時(shí),因?yàn)閿?shù)組的擴(kuò)容問(wèn)題,性能較低(轉(zhuǎn)移到更大的哈希表中).

Java默認(rèn)的散列單元大小全部都是2的冪，初始值為16（2的4次冪）。假如16條鏈表中的75%鏈接有數(shù)據(jù)的時(shí)候，則認(rèn)為加載因子達(dá)到默認(rèn)的0.75。HahSet開(kāi)始重新散列，也就是將原來(lái)的散列結(jié)構(gòu)全部拋棄，重新開(kāi)辟一個(gè)散列單元大小為32（2的5次冪）的散列結(jié)果，并重新計(jì)算各個(gè)數(shù)據(jù)的存儲(chǔ)位置。以此類(lèi)推下去.....

負(fù)載(加載)因子:0.75.-->hash表提供的空間是16 也就是說(shuō)當(dāng)?shù)竭_(dá)12的時(shí)候就擴(kuò)容

3.排重機(jī)制的實(shí)現(xiàn)

假如我們有一個(gè)數(shù)據(jù)(散列碼76268)，而此時(shí)的HashSet有128個(gè)散列單元，那么這個(gè)數(shù)據(jù)將有可能插入到數(shù)組的第108個(gè)鏈表中(76268%128=108)。但這只是有可能，如果在第108號(hào)鏈表中發(fā)現(xiàn)有一個(gè)老數(shù)據(jù)與新數(shù)據(jù)equals()=true的話(huà)，這個(gè)新數(shù)據(jù)將被視為已經(jīng)加入，而不再重復(fù)丟入鏈表。

4.優(yōu)點(diǎn)

哈希表的插入和查找是很優(yōu)秀的.

對(duì)于查找:直接根據(jù)數(shù)據(jù)的散列碼和散列表的數(shù)組大小計(jì)算除余后，就得到了所在數(shù)組的位置，然后再查找鏈表中是否有這個(gè)數(shù)據(jù)即可。因?yàn)閿?shù)組本身查找速度快,所以查找的效率高低體現(xiàn)在鏈表中，但是真實(shí)情況下在一條鏈表中的數(shù)據(jù)又很少，有的甚至沒(méi)有,所以幾乎沒(méi)有什么迭代的代價(jià)。所以散列表的查找效率建立在散列單元所指向的鏈表中數(shù)據(jù)的多少上.

對(duì)于插入:數(shù)組的插入速度慢,而鏈表的插入速度快.當(dāng)我們使用哈希表時(shí),不需要更改數(shù)組的結(jié)構(gòu),只需要在找到對(duì)應(yīng)的數(shù)組下標(biāo)后,進(jìn)入對(duì)應(yīng)的鏈表,操作鏈表即可.所以hash表的整體插入速度也很快.

5.模擬實(shí)現(xiàn)代碼

Node類(lèi)

```

public class Node {

// key、value模擬鍵值對(duì)的數(shù)據(jù)

    public Integer key;

    public String value;

    // 下一節(jié)點(diǎn)的引用

    public Node next;

    public Node() {

    }

    public Node(int key, String value) {

        this.key = key;

        this.value = value;

    }

}

```

MyLinkedList類(lèi)

```

    public class MyLinkedList {

    // 根節(jié)點(diǎn)

    private Node root;

    public MyLinkedList() {

        root = new Node();

    }

    /**

     * 添加數(shù)據(jù)，key值必須唯一，如果重復(fù)值將被覆蓋

     * @param key

     */

    public void add(int key, String value) {

        Node newNode = new Node(key, value);

        Node current = root;

        while (current.next != null) {

            if(current.next.key == key) {

                current.next.value = value;

                return;

            }

            current = current.next;

        }

        current.next = newNode;

    }

    /**

     * 刪除數(shù)據(jù)

     * @param key

     * @return

     */

    public boolean delete(int key) {

        Node current = root;

        while (current.next != null) {

            if(current.next.key == key) {

                current.next = current.next.next;

                return true;

            }

            current = current.next;

        }

        return false;

    }

    /**

     * 根據(jù)key獲取value

     * @param key

     * @return

     */

    public String get(int key) {

        Node current = root;

        while (current.next != null) {

            if(current.next.key == key) {

                return current.next.value;

            }

            current = current.next;

        }

        return null;

    }

    /**

     * 遍歷鏈表，列出所有數(shù)據(jù)

     * @return

     */

    public String list() {

        String str = "";

        Node current = root.next;

        while (current != null) {

            str += "(" + current.key + "," + current.value + "),";

            current = current.next;

        }

        return str;

    }

    @Override

    public String toString() {

        return list();

    }

}

```

MyHashMap類(lèi)

```

// 哈希表

public class MyHashMap {

    // 鏈表數(shù)組，數(shù)組的每一項(xiàng)都是一個(gè)鏈表

    private MyLinkedList[] arr;

    // 數(shù)組的大小

    private int maxSize;

    /**

     * 空參構(gòu)造，默認(rèn)數(shù)組大小為10

     */

    public MyHashMap() {

        maxSize = 10;

        arr = new MyLinkedList[maxSize];

    }

    /**

     * 帶參構(gòu)造，數(shù)組大小自定義

     * @param maxSize

     */

    public MyHashMap(int maxSize) {

        this.maxSize = maxSize;

        arr = new MyLinkedList[maxSize];

    }

    /**

     * 添加數(shù)據(jù)，key值必須唯一

     * @param key

     * @param value

     */

    public void put(int key, String value) {

        int index = getHashIndex(key);

        if(arr[index] == null) {

            arr[index] = new MyLinkedList();

        }

        arr[index].add(key, value);

    }

    /**

     * 刪除數(shù)據(jù)

     * @param key

     * @return

     */

    public boolean delete(int key) {

        int index = getHashIndex(key);

        if(arr[index] != null) {

            return arr[index].delete(key);

        }

        return false;

    }

    /**

     * 根據(jù)key獲取value

     * @param key

     * @return

     */

    public String get(int key) {

        int index = getHashIndex(key);

        if(arr[index] != null) {

            return arr[index].get(key);

        }

        return null;

    }

    /**

     * 獲取數(shù)組下標(biāo)

     * @param key

     * @return

     */

    private int getHashIndex(Integer key) {

        return key.hashCode() % maxSize;

    }

    /**

     * 遍歷數(shù)組中所有鏈表的數(shù)據(jù)

     * @return

     */

    public String list() {

        String str = "[ ";

        for (int i = 0; i < maxSize; i++) {

            if(arr[i] != null) {

                str += arr[i].toString();

            }

        }

        str = str.substring(0, str.length()-1);

        str += " ]";

        return str;

    }

    @Override

    public String toString() {

        return list();

    }

}

```

測(cè)試類(lèi)

```

public class Test {

    public static void main(String[] args) {

        MyHashMap map = new MyHashMap(20);

        map.put(5, "aaa");

        map.put(8, "bbb");

        map.put(3, "ccc");

        map.put(8, "bbb");

        map.put(2, "ddd");

        map.put(9, "eee");

        System.out.println(map);

        System.out.println(map.get(3));

        System.out.println(map.delete(2));

        System.out.println(map);

    }

}

“Hash表怎么實(shí)現(xiàn)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！