哈希表的实现（Java）

哈希表的实现（java）

前言

由于我有点累，不想写太多解释，晚点补充。

一、节点类

哈希表节点类我们具有四个属性，分别是哈希值，键，值，还有一个指向下一个节点类的next指针。

    static class entry {
        int hash;//哈希码
        object key;//键
        object value;//值
        entry next;//指向下一个节点的指针

        public entry(int hash, object key, object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }

除了该节点类后，我们还设置了该数组的大小和size属性来记录数组所含个数。

    entry[] table = new entry[16];
    int size = 0;//元素个数

二、基本操作

1.查询操作

在哈希表的查询操作中,我们传入两个参数，分别是哈希码和键值。当传入哈希码后我们可以使用哈希码除以数组长度来计算该节点存入的位置。但由于数据量太大时，我们可以才有位运算加快计算速度。但有以下两个条件

-数组长度必须是2的n次方
-数组%数组长度 等价于 哈希码&（数组长度-1)

计算出位置后，进行判断头位置是否存在元素，如果不存在则返回null值。否则我们设置个p指针，遍历整个在该位置的链表直到找到该key，并返回值。

    object get(int hash, object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        //遍历链表
        entry p = table[idx];
        while (p != null) {
            //都是object对象比较，所有用equals
            if (p.key.equals(key)) {
                return p.value;
            }
            p = p.next;
        }
        return null;
    }

2.删除数据

代码如下（示例）：

     void put(int hash, object key, object value) {
        int idx = hash & (table.length - 1);
        //1.idx处有空位，直接新增
        if (table[idx] == null) {
            table[idx] = new entry(hash, key, value);
            // size++;
        } else {
            //2.idx处无空位，沿链表查找，有重复key更新，否则新增
            entry p = table[idx];
            while (p != null) {
                if (p.key.equals(key)) {
                    p.value = value;//更新操作
                    return;
                }
                if (p.next == null) {
                    //什么时候退出循环
                    break;
                }
                p = p.next;
            }
            p.next = new entry(hash, key, value);
            // size++;
        }
        size++;//因为if里面和else里面都size++，可以提出来
    }

3.增加数据

   object remove(int hash, object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        entry p = table[idx];
        entry prev = null;
        while (p != null) {
            if (p.key.equals(key)) {
                //找到删除
                if (prev == null) {
                    table[idx] = p.next;
                } else {
                    prev.next = p.next;
                }
                size--;
                return p.value;
            }
            prev = p;//先记录当前节点，在更新
            p = p.next;
        }
        return null;
    }

4.完整代码

package com.itheima.hash;

public class hashtable {
    static class entry {
        int hash;//哈希码
        object key;//键
        object value;//值
        entry next;

        public entry(int hash, object key, object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    entry[] table = new entry[16];
    int size = 0;//元素个数

    //根据hash获取value
    /*因为除法运算效率低，所有可以替换为位运算
        -前提：数组的长度是2的n次方
        -数组%数组长度 等价于 hash&（数组长度-1）
     */
    object get(int hash, object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        //遍历链表
        entry p = table[idx];
        while (p != null) {
            //都是object对象比较，所有用equals
            if (p.key.equals(key)) {
                return p.value;
            }
            p = p.next;
        }
        return null;
    }

    //向hash表存入新value，如果key重复，则更新value
    void put(int hash, object key, object value) {
        int idx = hash & (table.length - 1);
        //1.idx处有空位，直接新增
        if (table[idx] == null) {
            table[idx] = new entry(hash, key, value);
            // size++;
        } else {
            //2.idx处无空位，沿链表查找，有重复key更新，否则新增
            entry p = table[idx];
            while (p != null) {
                if (p.key.equals(key)) {
                    p.value = value;//更新操作
                    return;
                }
                if (p.next == null) {
                    //什么时候退出循环
                    break;
                }
                p = p.next;
            }
            p.next = new entry(hash, key, value);
            // size++;
        }
        size++;//因为if里面和else里面都size++，可以提出来
    }

    //根据hash码删除，返回删除元素
    object remove(int hash, object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        entry p = table[idx];
        entry prev = null;
        while (p != null) {
            if (p.key.equals(key)) {
                //找到删除
                if (prev == null) {
                    table[idx] = p.next;
                } else {
                    prev.next = p.next;
                }
                size--;
                return p.value;
            }
            prev = p;//先记录当前节点，在更新
            p = p.next;
        }
        return null;
    }
}