欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HashMap

程序员文章站 2023-09-09 12:33:51
1、哈希表散列表,是根据关键码值(Key)进行访问的数据结构,也就是说,通过将Key映射到表中一个位置来获取记录,加快查找的速度,这个映射函数叫做撒案列函数,存放记录的结构称之为散列表寻址容易,删除插入也容易的数据结构通常以下几种方式构造哈希函数1)直接定址法 key address(key) = a*key + b2)平方取中法 key 108 109 110 = 108^2 109^2 110^23)折叠法 key -> 拆分为几部分 区域号-书架号-图书编号4)除留取余...

1、哈希表

  • 散列表,是根据关键码值(Key)进行访问的数据结构,也就是说,通过将Key映射到表中一个位置来获取记录,加快查找的速度,这个映射函数叫做撒案列函数,存放记录的结构称之为散列表
  • 寻址容易,删除插入也容易的数据结构
    通常以下几种方式构造哈希函数
  • 1)直接定址法 key address(key) = a*key + b
  • 2)平方取中法 key 108 109 110 = 108^2 109^2 110^2
  • 3)折叠法 key -> 拆分为几部分 区域号-书架号-图书编号
  • 4)除留取余法 key -> hash表的最大长度m 取不大于m的质数 key%质数
    解决冲突
  • 1)开放地址法 12 13 25 23 hash表的长度14 hash函数key%13
  • 2)链地址法
    2、HashMap的使用
  • HashMap基于哈希表(散列表)非同步实现的,哈希表对应的接口是Map接口(非线程安全)
  • jdk1.8之前,HashMap都是采用数组+链表实现的,即使用链地址法处理哈希冲突,不同的key值可能得到同样的散列码,统一hash值的节点都存储在一个链表中的,但是当链表中的元素越来越多的时候,通过key去查找的效率反而从O(1)->O(N)。jdk1.8中,HashMap采用数组+链表+红黑树的结构实现,当前链表的长度超过阀值8,将链表转换为红黑树,红黑树中的元素个数小于6,将红黑树再转换为链表

自定义HashMap,hash算法直接使用HashMap中的hash算法,解决哈希冲突

  • 采用链地址法,即链表+数组实现,包括方法有put(K key, V value), get(K key),

  • remove(K key)等方法

  • hashCode方法是将引用类型的内存地址转换为一个32位的整型返回,所以存在一定的限制,导致两个不同对象有可能hashCode也会相等,这样的话比较了hash值还需要比较引用,才能够保证两个对象完全相等。

HashMap迭代器实现

  • 1)哈希表中数据分布是不连续的,在迭代器初始化的过程中必须先跳转到第一个非空数据节点
  • 2)当迭代器的下标到达当前桶的链表末尾时,迭代器下标跳转到下一个非空桶的第一个数据节点
class MyHashMap<K,V>{
    private Node<K, V>[] table;
    private int size;

    class Node<K,V>{
        protected K key;
        protected V value;
        protected int hash;
        protected Node<K, V> next;

        public Node(K key, V value, int hash) {
            this.key = key;
            this.value = value;
            this.hash = hash;
        }
    }

    public MyHashMap(int capacity){
        table = new Node[capacity];
    }

    public Iterator<Node<K, V>> iterator(){
        return new Itr();
    }

    class Itr implements Iterator<Node<K, V>>{
        private int currentIndex;//当前桶的位置
        private Node<K, V> nextNode;//返回的下一个数据节点
        private Node<K, V> currentNode; //上一次next返回的数据节点

        public Itr(){
            if(MyHashMap.this.isEmpty()){
                return;
            }
            for(int i=0; i < table.length; i++){
                currentIndex = i;
                Node<K, V> firstNode = table[i];
                if(firstNode != null){
                    nextNode = firstNode;
                    return;
                }
            }
        }

        @Override
        public boolean hasNext() {
            return nextNode != null;
        }

        @Override
        public Node<K, V> next() {
            //返回下一个数据节点
            currentNode = nextNode;
            //nextNode指向自己的next
            nextNode = nextNode.next;
            if(nextNode == null){
                //说明当前桶的链表已经遍历完毕
                //寻找下一个非空的桶
                for(int i=currentIndex+1; i<MyHashMap.this.table.length; i++){
                    //设置当前桶位置
                    currentIndex = i;
                    Node<K,V> firstNode = MyHashMap.this.table[currentIndex];
                    if(firstNode != null){
                        nextNode = firstNode;
                        break;
                    }
                }
                //nextNode保存的就是下一个非空的数据节点
            }
            return currentNode;
        }

        @Override
        public void remove() {
            if(currentNode == null){
                return;
            }
            K currentKey = currentNode.key;
            MyHashMap.this.remove(currentKey);
            currentNode = null;
        }
    }

    public void resize(){
        //扩容桶table
        Node<K, V>[] newTable = new Node[table.length * 2];
        for(int i=0; i<table.length; i++){
            //将oldTable中每一个位置映射到newTable中
            rehash(i, newTable);
        }
        this.table = newTable;
    }

    public void rehash(int index, Node<K,V>[] newTable){
        Node<K, V> currentNode = table[index];
        if(currentNode == null){
            return;
        }

        Node<K, V> lowListHead = null; //低位的头
        Node<K, V> lowListTail = null; //低位的尾
        Node<K, V> highListHead = null; //高位的头
        Node<K, V> highListTail = null; //高位的尾

        //currentNode表示oleTable下index位置中当前节点
        while(currentNode != null){
            //当前节点在newTable中的位置
            int newIndex = newTable.length-1 & hash(currentNode.key);

            if(newIndex == index){
                //映射到原先下标处
                if(lowListHead == null){
                    lowListHead = currentNode;
                    lowListTail = currentNode;
                }else{
                    lowListTail.next = currentNode;
                    lowListTail = lowListTail.next;
                }
            }else{
                //newIndex与index不等,映射到高位下标处
                if(highListHead == null){
                    highListHead = currentNode;
                    highListTail = currentNode;
                }else{
                    highListTail.next = currentNode;
                    highListTail = lowListTail.next;
                }
            }
            currentNode = currentNode.next;
        }
        //将lowList head->tail之前的节点链接到index位置
        if(lowListTail != null){
            newTable[index] = lowListHead;
            lowListHead.next = null;
        }

        //将highList head->tail之前的节点链接到index+table.length位置
        if(highListTail != null){
            newTable[index+this.table.length] = highListHead;
            highListHead.next = null;
        }
    }

    public int hash(Object key) {
        int h;
        return (h = key.hashCode()) ^ (h >>> 16);
    }

    public void put(K key, V value){
        //确定所要添加元素的位置
        int hash = hash(key);//散列码
        int index = table.length-1 & hash;//确定的位置

        //newNode -》table[index] == null || key在map不存在
        //table[index]已经存在数据
        //table[index]不存在数据
        Node<K, V> firstNode = table[index];//得到该位置的第一个节点
        if(firstNode == null){
            table[index] = new Node(key, value, hash);
            size++;
        }else{
            //第一种情况 key已经存在 考虑新值覆盖旧值
            //第二种情况 key不存在   封装一个新的node尾插法插入链表
            if(firstNode.key.equals(key)){
                firstNode.value = value; //新值替换旧值
            }else{
                Node<K,V> tmp = firstNode;
                while(tmp.next != null && !tmp.key.equals(key)){
                    tmp = tmp.next;
                }
                if(tmp.next == null){
                    if(tmp.key.equals(key)){
                        tmp.value = value; //新值替换旧值
                    }else{
                        tmp.next = new Node(key, value, hash);
                        size++;
                    }
                }else{
                    tmp.value = value;
                }
            }
        }
    }

    public boolean remove(K key){
        int hash = hash(key);
        int index = table.length-1 & hash;

        Node<K, V> firstNode = table[index];

        if(firstNode == null){
            return false;
        }else{
           if(firstNode.next == null){
               if(firstNode.key.equals(key) && firstNode.hash == hash){
                   //为什么判断key是否相等的同时还需要判断散列码
                   table[index] = null;
                   return true;
               }
           }
           Node<K,V> tmpPrev = firstNode;
           Node<K, V> tmp = firstNode.next;
           while(tmp.next != null){
               if(tmp.key.equals(key) && tmp.hash == hash){
                   //tmp之前节点的next指向tmp.next
                   tmpPrev.next = tmp.next;
                   size--;
               }else{
                   tmpPrev = tmp;
                   tmp = tmp.next;
               }
           }
        }
        return false;
    }

    public Node<K,V> get(K key){
        //获取对应key所在数组的index
        int hash = hash(key);//散列码
        int index = table.length - 1 & hash; //定位key记录所在的位置

        Node<K, V> firstNode = table[index];
        if (firstNode == null) {
            return null;
        }
        if (hash == firstNode.hash && key == firstNode.key) {
            return firstNode;
        } else {
            //遍历链表
            Node<K, V> currentNode = firstNode.next;
            while (currentNode != null) {
                if (currentNode.hash == hash && currentNode.key == key) {
                    return currentNode;
                }
                currentNode = currentNode.next;
            }
        }
        return null;
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

public class TestDemo11 {
    public static void main(String[] args) {
    }
}

java当中四种引用

  1. 强引用
  • 通过new出来对象所关联的引用称之为强引用,只要强引用存在,当前对象不会被回收
  1. 软引用
  • 通过SoftReference类实现,在系统内存即将要溢出的时候,才会回收软引用对象
  1. 弱引用
  • 通过WeakReference实现,只要发生GC,被弱引用关联的对象就会被回收掉
  1. 虚引用
  • 通过PhantomReference实现,无法通过虚引用获取对象实例,唯一作用就是在这个对象被回收时,能够收到一个通知

本文地址:https://blog.csdn.net/weixin_43751188/article/details/109626866

相关标签: java hashmap