拉链法哈希表

r囧r小猫 2021-11-19 14:54 300阅读 0赞

拉链法哈希表

2019-07-03  13:31:32

import java.io.ObjectInputStream;
    import java.util.ArrayList;
    import java.util.Iterator;
    
    /**
     * @ClassName SeparateChainHashST
     * @Author wangyudi
     * @Date 2019/7/2 22:25
     * @Version 1.0
     * @Description 拉链法散列表（哈希表）
     */
    public class SeparateChainHashST<Key, Value> {
        private int m;//数组大小
        private int n;//键值对数量
        private Chain<Key, Value>[] st;//存放链表的数组
        private ArrayList<Key> list; //用于迭代获取键的集合
    
        public SeparateChainHashST() {
            this(997);
        }
        public SeparateChainHashST(int m) {
            this.m = m;
            st = (Chain<Key, Value>[]) new Chain[m]; //实例化数组
            for (int i = 0; i < m; i++) {
                st[i] = new Chain<Key, Value>(); //数组每个元素都指向一个空链表
            }
            this.n = 0;
        }
    
        public int getSize(){
            return m;
        }
    
        /**
         * 为了保证每条链的大小保持在2~8，调整数组的大小到size
         * 将源哈希表中所有键值对插入到新哈希表中；然后将新哈希表中的成员给源哈希表
         * @param size
         */
        private void resize(int size){
            SeparateChainHashST<Key, Value> keyValueSeparateChainHashST = new SeparateChainHashST<>(size);
            for(int i=0;i<m;i++){
                for(Object[] o : st[i]){
                    keyValueSeparateChainHashST.put((Key)o[0],(Value)o[1]);
                }
            }
            this.m = keyValueSeparateChainHashST.m;
            this.st = keyValueSeparateChainHashST.st;
        }
    
        /**
         * 返回可迭代的对象
         *
         * @return
         */
        public Iterable<Key> keys() {
            list = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (Object[] o : st[i]) {
                    list.add((Key)o[0]);
                }
            }
            return list;
        }
    
        /**
         * 根据键的hashcode，计算每个键的索引值
         *
         * @param key
         * @return
         */
        private int hash(Key key) {
            return (key.hashCode() & 0x7FFFFFFF) % m;
        }
    
        /**
         * 向哈希表中放入一个键值对，如果存在相同的键则更新该键的值
         *
         * @param key
         * @param value
         */
        public void put(Key key, Value value) {
            if(n>8*m){
                resize(2*m);
            }
            int i = hash(key);//找到键所在的数组索引
            st[i].put(key, value);//将插入键值对的问题交给链表
            n++;
        }
    
        /**
         * 根据键，从哈希表获取相应的值；没有该键则返回null
         */
        public Value get(Key key) {
            int i = hash(key);
            return st[i].get(key);
        }
    
        /**
         * 从哈希表删除键值对，并返回被删除键的值。
         *
         * @param key
         * @return
         */
        public void delete(Key key) {
            int i = hash(key);
            if(st[i].delete(key)){
                n--;
            }
            if(n>0&&n<=2*m){
                resize(m/2);
            }
        }
    }
    
    
    /**
     * 链表类
     *
     * @param <Key>
     * @param <Value>
     */
    class Chain<Key, Value> implements Iterable<Object[]> {
        private Node first;
    
        private class Node {
            Key key;
            Value value;
            Node next;
    
            public Node(Key key, Value value, Node next) {
                this.key = key;
                this.value = value;
                this.next = next;
            }
        }
    
        public Value get(Key key) {
            for (Node i = first; i != null; i = i.next) {
                if (i.key == key) {
                    return i.value;
                }
            }
            return null;
        }
    
        public void put(Key key, Value value) {
            for (Node i = first; i != null; i = i.next) {
                if (i.key == key) {
                    i.value = value;
                    return; //找到相同的键
                }
            }
            first = new Node(key, value, first);//在头部加入键值队
        }
    
        /**
         * 删除单向链表中的某一个结点
         *
         * @param key
         * @return
         */
        public boolean delete(Key key) {
    //        if (first == null) {
    //            return false;
    //        }
    //        if (first.key == key) {  //判断首结点
    //            first = first.next;
    //            return true;
    //        }
            Node f = null; //保存前一结点的信息
            Node b = first;
            while (b != null && b.key != key) {
                f = b;
                b = b.next;
            }
            if (b != null) { //找到要删除的对象
                if(f==null){
                    first=b.next; //特殊处理
                }else {
                   f.next = b.next;
                }
                b.next = null;
                b = null;
                return true;
            }
            return false;
        }
    
        @Override
        public Iterator<Object[]> iterator() {
            return new Iterator() {
                Node i = first;
    
                @Override
                public boolean hasNext() {
                    if (i != null) return true;
                    return false;
                }
    
                @Override
                public Object[] next() {
                    Key tempkey = i.key;
                    Value tempValue = i.value;
                    Object[] info = new Object[]{(Object)tempkey,(Object)tempValue};
                    i = i.next;
                    return info;
                }
            };
        }
    //    public Iterator<Node> nodeIterator(){
    //        return new Iterator<Node>() {
    //            Node i = first;
    //            @Override
    //            public boolean hasNext() {
    //                if(i!=null)return true;
    //                return false;
    //            }
    //
    //            @Override
    //            public Node next() {
    //                Node temp = i;
    //                i = i.next;
    //                return temp;
    //            }
    //        };
    //    }
    }

public class TestCase {
        public static void main(String[] args) {
            SeparateChainHashST<Integer, String> separateChainHashST = new SeparateChainHashST<>(100);
            separateChainHashST.put(12,"12..");
            separateChainHashST.put(2,"2..");
            separateChainHashST.put(34,"34..");
            separateChainHashST.put(17,"17..");
            separateChainHashST.put(55,"55..");
            separateChainHashST.put(214,"214..");
            separateChainHashST.put(12,"12..");
            separateChainHashST.put(2,"2..");
            separateChainHashST.put(34,"34..");
            separateChainHashST.put(17,"17..");
            separateChainHashST.put(55,"55..");
            separateChainHashST.put(214,"214..");
            for(Integer i : separateChainHashST.keys()){
                System.out.println(i);
            }
    
            System.out.println("===============================================");
            separateChainHashST.delete(34);
            for(Integer i : separateChainHashST.keys()){
                System.out.println(i);
            }
            System.out.println("===============================================");
            System.out.println(separateChainHashST.get(55));
            System.out.println("===============================================");
            System.out.println(separateChainHashST.getSize());
        }
    }
    
    //结果
    2
    12
    214
    214
    17
    34
    55
    ===============================================
    2
    55
    12
    214
    214
    17
    ===============================================
    55..
    ===============================================
    50

转载于:https://www.cnblogs.com/youzoulalala/p/11125073.html