怎么在Java中实现哈希表

本篇文章为大家展示了怎么在Java中实现哈希表，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

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

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

六、哈希表的泛型实现

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;    }}

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));    }}

注意：

要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方 法，而且要做到 equals 相等的对象，hashCode 一定是一致的。
比如Student s1 和 s2 的id一样，得到的却是不同的value，所以要覆写hashCode 和 equals 方 法，如果不覆写，则使用的是Object类的hashCode 和 equals 方 法，比较的是地址。

重写之后

常用的java框架有哪些

1.springMVC，spring WEB mvc是一种基于Java的实现了Web MVC设计模式的请求驱动类型的轻量级Web框架。2.shiro，Apache Shiro是Java的一个安全框架。3.mybatis，MyBatis 是支持普通 sql查询，存储过程和高级映射的优秀持久层框架。4.dubbo，Dubbo是一个分布式服务框架。5.Maven，Maven是个项目管理和构建自动化工具。6.RabbitMQ，RabbitMQ是用Erlang实现的一个高并发高可靠AMQP消息队列服务器。7.Ehcache，EhCache 是一个纯Java的进程内缓存框架。

上述内容就是怎么在Java中实现哈希表，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注编程网精选频道。