一文彻底搞定Java哈希表和哈希冲突

一、什么是哈希表?

哈希表也叫散列表,它是基于数组的。这间接带来了一个优点:查找的时间复杂度为 O(1)、当然,它的插入时间复杂度也是 O(1)。还有一个缺点:数组创建后扩容成本较高。
哈希表中有一个“主流”思想:转换。一个重要的概念是将「键」或「关键字」转换成数组下标。这由“哈希函数”完成。

二、什么是哈希函数?

由上,其作用就是将非 int 的键/关键字转化为 int 的值,使可以用来做数组下标。
比如,HashMap 中就这样实现了哈希函数:

static final int hash(Object key){
	int h;
	return (key==null)?0:(h=key.hashCode())^(h>>>16);   // 通过异或提高hash的“散列度”,降低冲突
}

其中利用了 hashCode 完成转换。虽然哈希函数有很多种实现,但都应当满足这三点:

  • 计算得到的是非负整数;
  • 如果 key1==key2,则 hash(key1)==hash(key2)
  • 如果 key1!=key2,则 hash(key1)!=hash(key2)

并不是所有的键/关键字都需要被转换才能做下标(索引)就像 JS 中也有类似的、但仅用于检测键是否能用来做数组下标的方法:JavaScript数组索引检测中的数据类型问题

三、什么是哈希冲突?

上面提到了 hashMap —— 一个java中提供的数据集。我们先来了解下:首先,hashMap 本质上是一个容器,它为了达到快速索引的目的,使用了数组结构“快速定位”的特性。
hashMap 中为了更快找到插入的值,建立了插入值和数组下标的关系:pos(下标)=key(值)%size(数组大小)

比如:数组长度为10

1.插入100,有100%10=0;

2.插入201,有201%10=1;

3.插入403,有403%10=3;

但是如果这样设计的话,我现在再插入200,会怎么样?
这就是数组的一个缺点:插入特殊值比较“费劲”。不如我们干脆将数组涉及成这样:

引入链表特性,一个节点就包括一个值和一个next指针。

现在再插入上面那些值,就变成了这样:

这时候如果再插入值300,怎么做?

类似这样(当两个或以上的key的pos相同,且key不同)其实就是我们提到的“hash冲突”,而 hashMap 中解决hash冲突的方法就是上面说的“单链表”!
但是这又有一个问题:虽然用有序链表的方式可以减少不成功的查找时间(因为只要有一项比查找值大,就说明没有我们需要查找的值),但是不能加快成功的查找。如果冲突的链表太长,则链表查找时需要从“头”遍历的劣势就暴露出来了 —— 针对这个问题,JDK1.8后用 红黑树 做了优化!

但是我们先撇开红黑树,用单链表的形式说明一下哈希表的操作:

/**
 * 链表基类:链表法解决哈希冲突用的是有序链表!
*/
public class SortedLinkList {
    private Link first;
    public SortedLinkList(){
        first = null;
    }
    /**
     * 链表插入
     * @param link
     */
    public void insert(Link link){
        int key = link.getKey();
        Link previous = null;
        Link current = first;
        while (current!=null && key >current.getKey()){
            previous = current;
            current = current.next;
        }
        if (previous == null)
            first = link;
        else
            previous.next = link;
        link.next = current;
    }

    /**
     * 链表删除
     * @param key
     */
    public void delete(int key){
        Link previous = null;
        Link current = first;
        while (current !=null && key !=current.getKey()){
            previous = current;
            current = current.next;
        }
        if (previous == null)
            first = first.next;
        else
            previous.next = current.next;
    }

    /**
     * 链表查找
     * @param key
     * @return
     */
    public Link find(int key){
        Link current = first;
        while (current !=null && current.getKey() <=key){
            if (current.getKey() == key){
                return current;
            }
            current = current.next;
        }
        return null;
    }
}

链表法哈希表插入:

public void insert(int data) {
    Link link = new Link(data);
    int key = link.getKey();
    int hashVal = hash(key);
    array[hashVal].insert(link);
}

链表法哈希表查找:

public Link find(int key) {
    int hashVal = hash(key);
    return array[hashVal].find(key);
}

链表法哈希表删除:

public Link find(int key) {
    int hashVal = hash(key);
    return array[hashVal].find(key);
}

除了链表法,解决哈希冲突还有一个方法:开放寻址法。
在开放地址法中,若数据不能直接存放在哈希函数计算出来的数组下标时,就需要寻找其他位置来存放。在开放地址法中有三种方式来寻找其他的位置,分别是

  • 线性探测
  • 二次探测
  • 再哈希法

到此这篇关于一文彻底搞定Java哈希表和哈希冲突的文章就介绍到这了,更多相关Java哈希表和哈希冲突内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • JAVA中哈希表HashMap的深入学习

    深入浅出学Java--HashMap 哈希表(hash table) 也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对java集合框架中HashMap的实现原理进行讲解,并对JDK7的HashMap源码进行分析. 一.什么是哈希表 在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能 数组:采用一段连续的存储单元来存储数据.对于指定下标的查找,时间复杂度为O(1):通过给定值进

  • java中哈希表及其应用详解

    哈希表也称为散列表,是用来存储群体对象的集合类结构. 什么是哈希表 数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系.当要查找一个对象时,只能以某种顺序(如顺序查找或二分查找)与各个元素进行比较,当数组或向量中的元素数量很多时,查找的效率会明显的降低. 一种有效的存储方式,是不与其他元素进行比较,一次存取便能得到所需要的记录.这就需要在对象的存储位置和对象的关键属性(设为 k)之间建立一个特定的对应关系(设为 f),使每个对象与一个唯一的存储位置

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • Java数据结构与算法入门实例详解

    第一部分:Java数据结构 要理解Java数据结构,必须能清楚何为数据结构? 数据结构: Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构. 而一个数据结构的设计过程分成抽象层.数据结构层和实现层. 数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构. 一.Java数据结构之:线性数据结构 线性数据结构:常见的

  • java数据结构和算法中哈希表知识点详解

    树的结构说得差不多了,现在我们来说说一种数据结构叫做哈希表(hash table),哈希表有是干什么用的呢?我们知道树的操作的时间复杂度通常为O(logN),那有没有更快的数据结构?当然有,那就是哈希表: 1.哈希表简介 哈希表(hash table)是一种数据结构,提供很快速的插入和查找操作(有的时候甚至删除操作也是),时间复杂度为O(1),对比时间复杂度就可以知道哈希表比树的效率快得多,并且哈希表的实现也相对容易,然而没有任何一种数据结构是完美的,哈希表也是:哈希表最大的缺陷就是基于数组,因

  • Java数据结构之哈夫曼树概述及实现

    一.与哈夫曼树相关的概念 概念 含义 1. 路径 从树中一个结点到另一个结点的分支所构成的路线 2. 路径长度 路径上的分支数目 3. 树的路径长度 长度从根到每个结点的路径长度之和 4. 带权路径长度 结点具有权值, 从该结点到根之间的路径长度乘以结点的权值, 就是该结点的带权路径长度 5. 树的带权路径长度 树中所有叶子结点的带权路径长度之和 二.什么是哈夫曼树 定义: 给定n个权值作为n个叶子结点, 构造出的一棵带权路径长度(WPL)最短的二叉树,叫哈夫曼树(), 也被称为最最优二叉树.

  • Java 哈希表详解(google 公司的上机题)

    1 哈希表(散列)-Google 上机题 1) 看一个实际需求,google 公司的一个上机题: 2) 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的 id 时,要求查 找到该员工的 所有信息. 3) 要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列) 2 哈希表的基本介绍 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构.也就是说,它通 过把关键码值映射到表中一个位置

  • Java 单链表数据结构的增删改查教程

    我就废话不多说了,大家还是直接看代码吧~ package 链表; /** * *1)单链表的插入.删除.查找操作: * 2)链表中存储的是int类型的数据: **/ public class SinglyLinkedList { private Node head = null; //查找操作 public Node findByValue(int value){ Node p = head; //从链表头部开始查找 while(p.next != null && p.data != va

  • 一文彻底搞定Java哈希表和哈希冲突

    一.什么是哈希表? 哈希表也叫散列表,它是基于数组的.这间接带来了一个优点:查找的时间复杂度为 O(1).当然,它的插入时间复杂度也是 O(1).还有一个缺点:数组创建后扩容成本较高. 哈希表中有一个"主流"思想:转换.一个重要的概念是将「键」或「关键字」转换成数组下标.这由"哈希函数"完成. 二.什么是哈希函数? 由上,其作用就是将非 int 的键/关键字转化为 int 的值,使可以用来做数组下标. 比如,HashMap 中就这样实现了哈希函数: static f

  • 一文彻底搞懂Java和JDK的版本命名问题

    Java是面向对象的编程语言,在我们开发Java应用的程序员的专业术语里,Java这个单词其实指的是Java开发工具,也就是JDK(Java Development Kit).所以我们常常在CSDN等各大程序员论坛讨论到安装Java8或者JDK8或者JDK1.8或J2SE8或J2SE1.8或J2SE8或J2SE1.8,其实这3个专业词汇的概念是一样的. 告诉庆哥,你对Java的版本号以及JDK的命名真正清楚嘛?比如: Java8 Java SE 8.0 JDK1.8 -- 知道这些是怎么回事嘛?

  • 10分钟搞定Java并发队列

    前言 如果按照用途与特性进行粗略的划分,JUC 包中包含的工具大体可以分为 6 类: 执行者与线程池 并发队列 同步工具 并发集合 锁 原子变量 在并发系列中,主要讲解了 执行者与线程池,同步工具,锁 , 在分析源码时,或多或少的提及到了「队列」,队列在 JUC 中也是多种多样存在,所以本文就以「远看」视角,帮助大家快速了解与区分这些看似「杂乱」的队列 并发队列 Java 并发队列按照实现方式来进行划分可以分为 2 种: 阻塞队列 非阻塞队列 如果你已经看完并发系列锁的实现,你已经能够知道他们实

  • 5分钟搞定java单例模式

    目录 单例模式 单例模式的运用场景 实现单例模式的方法思路 实现单例模式的方式 01懒汉单例式 02饿汉单列式 03静态内部类的方式 04枚举 资源加载和性能区别 单例模式 单例模式(Singleton),也叫单子模式,是一种常用的软件设计模式.在应用这个模式时,单例对象的类必须保证只有一个实例存在.许多时候整个系统只需要拥有一个的全局对象,这样有利于我们协调系统整体的行为. 比如在某个服务器程序中,该服务器的配置信息存放在一个文件中,这些配置数据由一个单例对象统一读取,然后服务进程中的其他对象

  • 一文教你搞定Java Optional类判空操作

    目录 概述 创建Optional实例 获取Optional中的值 判断Optional是否为空 Optional中的过滤.转换方法 概述 最近项目组内做code review,充斥着大量的.原始的.丑陋的判空语句,大致类似下面的代码: if (user != null) { Address address = user.getAddress(); if (address != null) { Country country = address.getCountry(); if (country

  • 带你轻松搞定Java面向对象的编程--数组,集合框架

    目录 一.数组 1.数组的定义 2.数组的声明 3.数组的初始化 二.集合概述 三.Collection接口 1.Collection接口概述 2.集合框架的三个组件 3.Iterator接口 四.List接口 1.ArrayList类 2.LinkedList类 五.Set接口 1.HashSet类 六.Map接口 1.HashMap类 七.泛型 总结 一.数组 1.数组的定义 数组是为了解决同类数据整合摆放而提出的,可以理解为一组具有相同类型的变量的集合,它的每个元素都具有相同的数据类型.

  • 带你快速搞定java多线程

    目录 1.什么是线程 2.线程的状态 3.怎么通俗理解进程,线程? 4.线程和进程的区别 5.什么是线程安全 6.如何创建线程 总结: 1.什么是线程 线程是操作系统调度的最小单元,也叫轻量级进程.它被包含在进程之中,是进程中的实际运作单位.同一进程可以创建多个线程,每个进程都有自己独立的一块内存空间.并且能够访问共享的内存变量. 2.线程的状态 线程的状态一般看到的也就是Runable 和blocked ,最多的还是blocked,因为cpu的时间片很短,切换的很快等待IO,等待临界资源.大概

  • 带你快速搞定java多线程(4)

    目录 1.AQS 是什么? 2.AQS 模型 3.AQS state 4.AQS 两种资源共享方式: 5.模板方式实现自定义 6.锁的分类:公平锁和非公平锁,乐观锁和悲观锁 7.CAS 8.总结 1.AQS 是什么? AQS 是类 AbstractQueuedSynchronizer的简称,也是常用锁的基类,比如常见的ReentrantLock,Semaphore,CountDownLatch 等等. AQS提供了一种实现阻塞锁和一系列依赖FIFO等待队列的同步器的框架.是Java提供的一种模板

  • 一文彻底搞懂java多线程和线程池

    目录 什么是线程 一. Java实现线程的三种方式 1.1.继承Thread类 1.2.实现Runnable接口,并覆写run方法 二. Callable接口 2.1 Callable接口 2.2 Future接口 2.3 Future实现类是FutureTask. 三. Java线程池 3.1.背景 3.2.作用 3.3.应用范围 四. Java 线程池框架Executor 4.1.类图: 4.2 核心类ThreadPoolExecutor: 4.3 ThreadPoolExecutor逻辑结

  • 四步轻松搞定java web每天定时执行任务

    本文介绍了java web每天定时执行任务,分享给大家,具体如下: 第一步: package com.eh.util; import java.util.Calendar; import java.util.Date; import java.util.Timer; /** * java定时任务,每天定时执行任务 * @author wls * */ public class TimerManager { //时间间隔 private static final long PERIOD_DAY =

随机推荐