HashMap仿写

阳光穿透心脏的1/2处 2023-10-01 21:47 2阅读 0赞

该map中只实现了简单的put()、get()、resize()方法，通过数组+链表实现，博主水平过低，写不出红黑树

代码已经上传至gitee:[HashMap: HashMap仿写][HashMap_ HashMap]

部分代码展示：

对节点的处理

public class Node<K,V> {
        K key;//key
        V value;//value
        int hash;//哈希值
        Node<K,V> next;//防止哈希冲突的next节点
    
        public Node(K key, V value, int hash, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", hash=" + hash +
                    ", next=" + next +
                    '}';
        }
    }

put方法

void put(K key,V value){
            //是数组下标
            int hash = hash(key);
            //判断是否发生覆盖
            boolean flag = true;
            //判断数组下标位置是否为空
            if (this.table[hash] == null){
                this.table[hash] = new Node<>(key,value,hash,null);
                System.out.println("put元素key:"+key+" value:"+value+" hash:"+hash);
            }else {
                Node<K,V> head = this.table[hash];
                //发生哈希冲突，遍历链表
                while (head != null){
                    if (key == head.key){
                        head.value = value;
                        System.out.println("覆盖");
                        flag = false;
                        break;
                    }
                    //如果哈希冲突没有发生覆盖，使用尾插法，使链表最后一个节点指向新节点
                    if (head.next == null){
                        head.next = new Node<>(key,value,hash,null);
                        System.out.println("put元素key:"+key+" value:"+value+" hash:"+hash);
                        break;
                    }
                    head = head.next;
                }
                if (flag) this.size++;
                //判断map容量是否超出范围 = 数组长度 * 负载因子，超出则扩容
                if (size > capacoty * loadFactor){
                    System.out.println("进行扩容");
                    resize();
                }
    
            }
        }

get方法

V get(K key){
            //计算数组下标
            int hash = hash(key);
            V value = null;
            if (this.table[hash] == null){
                return value;
            }else {//遍历链表
                Node<K,V> head = this.table[hash];
                while (head != null){
                    if (head.key == key){
                        value = head.value;
                        break;
                    }
                    head = head.next;
                }
                return value;
            }
        }

[HashMap_ HashMap]: https://gitee.com/kan-peizhen_admin_admin/hash-map.git