IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 哈希表和Map接口 -> 正文阅读

[数据结构与算法]哈希表和Map接口

目录

哈希表

避免哈希冲突

设计哈希函数

调节负载因子

解决哈希冲突

开放地址法

线性探测法

二次探测法

链地址法

Map接口

HashMap集合

HashMap的底层实现

常用方法

put方法---添加元素

get方法--根据key值得到value值

?遍历

?LinkedHashMap集合:保证元素的输入顺序

?TreeMap集合

hashtree和hashmap的区别

1、输出的有序性

?2.对null的要求

?3、性能分析


我们查找一个数据时,遍历元素的查找时间复杂度O(n),二分查找的时间复杂度O(log2N)……那有没有可能查找的时间复杂度在O(1)呢?这就是哈希表

哈希表

根据某一种映射关系,将元素存储在某一个特定位置,查找元素时,根据这个映射关系得到存储位置---》这就是哈希表

这个映射关系就是哈希函数

但是有一个问题,如果我还有一个元素是33呢,根据上图的映射关系,33%11==0,应该放在0下标,但是0下标已经有一个元素11了,33又放到哪里?这种产生的冲突就是哈希冲突

那么如何避免,如何解决哈希冲突呢?

避免哈希冲突

设计哈希函数

设计更好的哈希函数,可以尽量避免哈希冲突

好的哈希函数满足的条件:

  • 哈希函数的定义域必须包括了所有的数据。如果哈希表长度是m,那么所有的数据使用哈希函数得到的下标都必须在0~m-1之间
  • 元素按照哈希函数得到的存储位置尽可能的均匀
  • 哈希函数尽量简单

常用的哈希函数设计方法:

1、直接定址法:hash(key)=A*key+b

线性函数:y=kx+b---》均匀的分布在线性函数附近

2、除留余数法:hash(key)=key%a---得到的下标位置[0~a-1]

调节负载因子

负载因子=存入哈希表的元素个数/哈希表的长度

如果负载因子过大,冲突的可能性越大,那么就可以来增大哈希表的长度来减少发生冲突的可能

解决哈希冲突

冲突无法完全避免,我们要想办法解决冲突

开放地址法

只要数组有空元素,找到空元素位置存放冲突元素

线性探测法

?H=(hash(key)+d)%m

二次探测法

H=(hash(key)±a^2)%m

链地址法

数组+链表

??jdk1.8开始,?当链表长度超过8且数组长度超过64,这时候链表会转为红黑树(查找非常高效的树)

通常情况下,哈希表插入和查找的时间复杂度O(1)

Map接口

一个人的身份证号唯一对应了这个人,这种具有对应关系的数据的存储就需要Map接口

Map接口是一种双列集合,每个元素都包含一个键对象Key和值对象Value,键和值之间存在着某一种对应关系,称为映射

Map接口中的映射关系是一对一的,一个键对象对应着唯一的值对象,Key和Value都可以是任意的数据类型,并且键对象Key不允许重复,这样通过key可以找到唯一指定的value(key---value模型)

HashMap集合

HashMap集合是Map接口的实现类,用于存储键值之间的映射关系,键不能重复,且集合元素是无序的

HashMap的底层实现

hashmap的底层是一个哈希表,这个哈希表使用链表解决冲突(JDK1.8后,当链表长度大于8且数组长度>64,链表变成红黑树)

常用方法

put方法---添加元素

?如何添加元素:?

1、根据提供的key(键值)得到对应的hash值

2、根据对应的hash值,找到哈希表数组的相对应存储位置

3、判断这个数组位置是不是有结点,没有结点直接插入结点;数组位置有结点,判断链表中是否有结点的key和插入结点的key相同,相同意味着value值要更新;如果不存在一个结点的key和插入结点的key相同,那么意味着要在链表插入结点(jdk1.8之后使用尾插法)

4、插入一个元素,就要计算负载因子,负载因子越大,产生冲突的可能性就越大,可以通过增大数组长度来减小负载因子。(数组不是单纯的扩容,数组长度改变,哈希函数改变,所有元素都需要重新哈希入新的数组)

简单的模拟实现:

public class Myhashmap {
    class Node {
        int key;
        int value;
        Node next;

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

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                 "}";
        }
    }

    private int count = 0;//记录存入的数据个数
    private final float loadFactor = 0.75f;//hashmap默认的装载因子是0.75f
    Node[] table = new Node[10];//table存放的是new Node这个实例化对象的引用,现在存放是null

    /**
     * 根据key插入元素value
     */
    public void put(int key, int value) {
        //第一步,设计hash函数,得到hash值
        int hash = key % table.length;

        //第二步:插入结点的key已经存在
        Node cur = table[hash];
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        //第三步:插入结点的key不存在(jdk1.8后使用尾插法)
        cur = table[hash];
        Node newode = new Node(key, value);
        if (cur == null) {
            table[hash] = newode;
            count++;
            loadFactor(key, value);
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newode;
        count++;
        //第四步,计算装载因子(存入的元素个数除以数组长度)
        loadFactor(key, value);
    }

    private void loadFactor(int key, int value) {
        if (count * 1.0f / table.length > loadFactor) {//数组扩容,hashmap数组2倍扩容
            reseize();
        }
    }

    private void reseize() {
        Node[] newtable = new Node[table.length * 2];
        //遍历之前的数组,例如hash(4)存储的key=14就要重新hash到新数组的hash(14)位置
        for (int i = 0; i < table.length; i++) {
            Node cur = table[i];
            Node newnode;
            while (cur != null) {//链表的每一个元素全部重新哈希(jdk1.8后使用尾插法,其实头插简单)
                int hash = cur.key % newtable.length;
                newnode = newtable[hash];
                Node curNext = cur.next;
                cur.next = null;
                if (newnode == null) {
                    newtable[hash] = cur;
                    cur = curNext;
                    continue;
                }
                while (newnode.next != null) {
                    newnode = newnode.next;
                }
                newnode.next = cur;
                cur = curNext;
            }
        }
        table = newtable;
    }
    public void print() {
        for (int i = 0; i < table.length; i++) {
            Node node = table[i];
            while (node != null) {
                System.out.println(node);
                node = node.next;
            }
        }
    }
}

hashmap的源码设置:

数组长度默认16,二倍扩容,负载因子是0.75,当链表长度超过8并且数组长度超过64的时候,链表转化为红黑树

get方法--根据key值得到value值

模拟实现:

 public Node get(int key) {
        for (int i = 0; i < table.length; i++) {
            Node node = table[i];
            while (node != null) {
             if(node.key==key)
                 return node;
                node = node.next;
            }
        }
        return null;
    }

?hashmap的泛型类实现:

class Person{
    int ID;
    public Person(int ID) {
        this.ID = ID;
    }

    @Override
    public String toString() {
        return "Person{" +
                "ID=" + ID +
                '}';
    }
}

public class hash {
    public static void main(String[] args) {
        Person person=new Person(123);
        Person person1=new Person(123);
        System.out.println(person.hashCode());
        System.out.println(person1.hashCode());
    }
}

hashCode方法可以将引用类型转化为整数,但是我们想让身份证后三位相同的人,产生相同的hash值,发现做不到,产生的整数值是不相同的

?但是,我们重写equals and?hashCode方法之后:

?就会产生相同的整数

?为什么要同时重写equals()和?hashCode()方法呢?

equals()用于比较是否相等,hashCode()用于生成整数

hashCode()相同,equal()不一定相同

equals()相同,hashCode()一定相同

public class Myhashmap<K,V> {
     class Node <K,V>{
        K key;
        V value;
        Node <K,V>next;

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

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                 "}";
        }
    }

    private int count = 0;//记录存入的数据个数
    private final float loadFactor = 0.75f;//hashmap默认的装载因子是0.75f
    Node <K,V>[] table = new Node [10];//table存放的是new Node这个实例化对象的引用,现在存放是null

    /**
     * 根据key插入元素value
     */
    public void put(K key, V value) {
        //第一步,设计hash函数,得到hash值
        int hash = key.hashCode() % table.length;

        //第二步:插入结点的key已经存在
        Node <K,V>cur = table[hash];
        while (cur != null) {
            if (cur.key .equals(key) ) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        //第三步:插入结点的key不存在(jdk1.8后使用尾插法)
        cur = table[hash];
        Node<K,V> newode = new Node<K,V>(key, value);
        if (cur == null) {
            table[hash] = newode;
            count++;
            loadFactor(key, value);
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newode;
        count++;
        //第四步,计算装载因子(存入的元素个数除以数组长度)
        loadFactor(key, value);
    }

    private void loadFactor(K key, V value) {
        if (count * 1.0f / table.length > loadFactor) {//数组扩容,hashmap数组2倍扩容
            reseize();
        }
    }

    private void reseize() {
        Node<K,V>[] newtable = new Node[table.length * 2];
        //遍历之前的数组,例如hash(4)存储的key=14就要重新hash到新数组的hash(14)位置
        for (int i = 0; i < table.length; i++) {
            Node<K,V> cur = table[i];
            Node<K,V> newnode;
            while (cur != null) {//链表的每一个元素全部重新哈希(jdk1.8后使用尾插法,其实头插简单)
                int hash = cur.key.hashCode() % newtable.length;
                newnode = newtable[hash];
                Node<K,V> curNext = cur.next;
                cur.next = null;
                if (newnode == null) {
                    newtable[hash] = cur;
                    cur = curNext;
                    continue;
                }
                while (newnode.next != null) {
                    newnode = newnode.next;
                }
                newnode.next = cur;
                cur = curNext;
            }
        }
        table = newtable;
    }
    public void print() {
        for (int i = 0; i < table.length; i++) {
            Node<K,V> node = table[i];
            while (node != null) {
                System.out.println(node);
                node = node.next;
            }
        }
    }
    public Node<K,V> get(int key) {
        for (int i = 0; i < table.length; i++) {
            Node<K,V> node = table[i];
            while (node != null) {
             if(node.key.equals(key))
                 return node;
                node = node.next;
            }
        }
        return null;
    }
}

?遍历

1、迭代器

    public static void main(String[] args) {
        Map <String,Integer> map=new HashMap<>();
        map.put("123",1);
        map.put("145",9);
        Set<String>set=map.keySet();//获取key值的集合
        Iterator  it=set.iterator();
        while(it.hasNext()){
            Object key=it.next();//获取key
            Object value=map.get(key);//获取key对应的value
            System.out.println(key+" "+value);
        }
    }

2、

  public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("123", 1);
        map.put("145", 9);
        Set set = map.entrySet();//将所有的键值对打包到一起,成为Set集合返回
        Iterator it=set.iterator();
        while(it.hasNext()){
            Map.Entry ret=(Map.Entry)(it.next());//将Iterator对象的其中一个转化为  Map.Entry<K,V>
            Object key=ret.getKey();
            Object value=ret.getValue();
            System.out.println(key+" "+value);
        }
    }

3、for-each

Lambda表达式的函数式接口BIConsumer

  public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("123", 1);
        map.put("145", 9);
       map.forEach((key,value)-> System.out.println(key+" "+value));
    }

?LinkedHashMap集合:保证元素的输入顺序

使用hashmap集合无法保证集合元素的存入和取出顺序

LinkedHashMap是hashmap的子类,内设双向链表来维护元素内部之间的关系,保证元素的输出顺序和存入顺序一致

  public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 9);
        map.put(3,0);
        map.put(2, 1);
        System.out.println(map);

        Map<Integer, Integer> map1 = new LinkedHashMap<>();
        map1.put(1, 9);
        map1.put(3,0);
        map1.put(2, 1);
        System.out.println(map1);
    }

?TreeMap集合

底层实现是一个红黑树

??TreeTree会自动对key值进行排序存储(String 类实现了Comparator接口)hashtree适用于key有序的情况下

hashtree和hashmap的区别

1、输出的有序性

hashmap的key值无顺序,hashtree的key有顺序

    public static void main(String[] args) {
        Map<Integer,String>map=new HashMap<>();
     map.put(78,"8");
        map.put(0,"8");
        map.put(89,"8");
        System.out.println(map);
        Map<Integer,String>maptree=new TreeMap<>();
        maptree.put(78,"8");
        maptree.put(0,"8");
        maptree.put(89,"8");
        System.out.println(maptree);
    }

?2.对null的要求

?hashmap可以让key和value都是null

1、key==null&&value==null ---存入键值对(null,null)

2、key==null&&value!=null ---不存入键值对,但是不会抛出异常

3、key!=null&&value==null ---存入键值对(key,null)

hashtree的key不能是null,value可以是null,否则抛出异常

  public static void main(String[] args) {
        Map<String,Integer> maptree=new TreeMap<>();
        maptree.put("hi",null);
        System.out.println(maptree);
        System.out.println(maptree.size());
    }

?3、性能分析

hashmap的底层是链表+数组,查找和插入的时间复杂度都是O(1)

hashtree的底层是红黑树,查找和插入的时间复杂度都是O(log2 N)

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-02-28 15:50:37  更:2022-02-28 15:53:44 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 16:50:19-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码