Java實(shí)現哈希表的基本功能

目錄

一、哈希表頭插法放入元素

/**
 * user：ypc；
 * date：2021-05-20;
 * time: 11:05;
 */
public class HashBuck {

    class Node {
        public int key;
        int value;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public int usedSize;
    public Node[] array;

    HashBuck() {
        this.array = new Node[8];
        this.usedSize = 0;
    }

    //JDk1.7及之前是頭插法
    public void put1(int key, int value) {
        int index = key % this.array.length;
        Node node = new Node(key, value);
        Node cur = array[index];

        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        node.next = array[index];
        array[index] = node;
        this.usedSize++;
        if (loadFactor() > 0.75) {
            resize1();
        }
    }
    public double loadFactor() {
        return this.usedSize / this.array.length * 1.0;
    }
}

二、哈希表尾插法放入元素

//JDK1.8是尾插法
    public Node findLast(Node head) {
        if (head == null) return head;
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }
    public void put2(int key, int value) {
        int index = key % this.array.length;
        Node node = new Node(key, value);
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        Node last = findLast(array[index]);
        if (last == null) {
            array[index] = node;
            this.usedSize++;
            return;
        }
        last.next = node;
        this.usedSize++;
        if (loadFactor() > 0.75) {
            resize2();
        }
    }

三、哈希表頭插、尾插擴容

public void resize1() {
        Node[] newArray = new Node[this.array.length * 2];
        for (int i = 0; i < this.array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                int index = cur.key % newArray.length;
                Node curNext = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
    }
    //resize尾插
    public void resize2() {
        Node[] newArray = new Node[this.array.length * 2];
        for (int i = 0; i < this.array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                int index = cur.key % newArray.length;
                Node curNext = cur.next;
                Node last = findLast(newArray[index]);
                if (last == null) {
                    newArray[index] = cur;
                    break;
                }
                last.next = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
    }

    public Node findLast(Node head) {
        if (head == null) return head;
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }

四、找到key對應的value

 public int get(int key) {
        int index = key % this.array.length;
        Node cur = this.array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }

五、運行結果

class HashBuckTest {
    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
       //頭插
        hashBuck.put1(9,451);
        hashBuck.put1(17,455);
       //尾插
       //hashBuck.put2(9,451);
       //hashBuck.put2(17,455);
        hashBuck.put1(2,45);
        hashBuck.put1(3,14);
        hashBuck.put1(4,52);
        hashBuck.put1(4,89);
        System.out.println(hashBuck.get(1));
        System.out.println("+=================");
    }
}

頭插

尾插

擴容

class HashBuckTest {
    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
//        hashBuck.put1(9, 451);
//        hashBuck.put1(17, 455);
        hashBuck.put1(1, 589);
        hashBuck.put1(2, 45);
        hashBuck.put1(3, 14);
        hashBuck.put1(4, 52);
        hashBuck.put1(4, 1);
        hashBuck.put1(6, 829);
        hashBuck.put1(7, 72);
        hashBuck.put1(8, 8279);
        hashBuck.put2(9,451);
        hashBuck.put2(15,455);
        hashBuck.put2(31,451);
        System.out.println(hashBuck.get(7));
        System.out.println(hashBuck.get(4));
        System.out.println(hashBuck.get(15));
        System.out.println(hashBuck.get(31));
    }
}

get

六、哈希表的泛型實(shí)現

public class HashBuck2<K, V> {

    static class Node<K, V> {
        public K key;
        public V val;
        public Node<K, V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node<K, V>[] array;
    public int usedSize;

    public HashBuck2() {
        this.array = (Node<K, V>[]) new Node[8];
    }

    public void put(K key, V val) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        Node<K, V> node = new Node<>(key, val);
        node.next = array[index];
        array[index] = node;
        this.usedSize++;
        if (loadFactor() > 0.75) {
            resize();
        }
    }

    public V get(K key) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
    public void resize() {
        Node[] newArray = new Node[this.array.length * 2];
        for (int i = 0; i < this.array.length; i++) {
            Node<K,V> cur = array[i];
            while (cur != null) {
                int hash = cur.key.hashCode();
                int index = hash % array.length;
                Node <K,V>curNext = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
    }
    public double loadFactor() {
        return this.usedSize / this.array.length * 1.0;
    }
}

/**
 * user：ypc；
 * date：2021-05-20;
 * time: 15:25;
 */
class Student{
    public int id;
    Student(int id){
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return id == student.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
class HashBuck2Test{
    public static void main(String[] args) {
        HashBuck2<Student,Integer> hashBuck2 = new HashBuck2<>();
        Student s1 = new Student(10001);
        Student s2 = new Student(10001);
        Student s3 = new Student(10003);
        hashBuck2.put(s1,89);
        hashBuck2.put(s1,60);
        hashBuck2.put(s2,94);
        hashBuck2.put(s3,100);
        System.out.println(hashBuck2.get(s1));
        System.out.println(hashBuck2.get(s2));
    }
}

注意：

要用自定義類(lèi)作為 HashMap 的 key 或者 HashSet 的值，必須覆寫(xiě) hashCode 和 equals 方 法，而且要做到 equals 相等的對象，hashCode 一定是一致的。
比如Student s1 和 s2 的id一樣，得到的卻是不同的value，所以要覆寫(xiě)hashCode 和 equals 方 法，如果不覆寫(xiě)，則使用的是Object類(lèi)的hashCode 和 equals 方 法，比較的是地址。

重寫(xiě)之后

七、為什么JDK1.7及之前使用頭插法而JDK1.8使用尾插法

hashmap用數組+鏈表。數組是固定長(cháng)度，鏈表太長(cháng)就需要擴充數組長(cháng)度進(jìn)行rehash減少鏈表長(cháng)度。如果兩個(gè)線(xiàn)程同時(shí)觸發(fā)擴容，在移動(dòng)節點(diǎn)時(shí)會(huì )導致一個(gè)鏈表中的2個(gè)節點(diǎn)相互引用，從而生成環(huán)鏈表

到此這篇關(guān)于Java實(shí)現哈希表的基本功能的文章就介紹到這了,更多相關(guān)哈希表基本功能實(shí)現內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！