精华内容
下载资源
问答
  • Java哈希表及其应用

    千次阅读 2018-05-16 21:46:48
    什么是哈希表 哈希表也称为散列表,是用来存储群体对象的集合类结构。 数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种...

    什么是哈希表
    哈希表也称为散列表,是用来存储群体对象的集合类结构。

    数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种顺序(如顺序查找或二分查找)与各个元素进行比较,当数组或向量中的元素数量很多时,查找的效率会明显的降低。

    一种有效的存储方式,是不与其他元素进行比较,一次存取便能得到所需要的记录。这就需要在对象的存储位置和对象的关键属性之间建立一个特定的对应关系,使每个对象与一个唯一的存储位置相对应。在查找时,只要根据待查对象的关键属性 k 计算 f(k)的值即可。如果此对象在集合中,则必定在存储位置 f(k)上,因此不需要与集合中的其他元素进行比较。称这种对应关系 f 为哈希(hash)方法,按照这种思想建立的表为哈希表

    Java使用哈希表类(Hashtable)来实现哈希表,以下是与哈希表相关的一些概念:
    容量(Capacity):Hashtable的容量不是固定的,随对象的加入其容量也可以自动增长。
    关键字(Key):每个存储的对象都需要有一个关键字,key可以是对象本身,也可以是对象的一部分(如某个属性)。要求在一个Hashtable中的所有关键字都是唯一的。
    哈希码(Hash Code):若要将对象存储到Hashtable上,就需要将其关键字key映射到一个整型数据,成为key的哈希码。
    项(Item):Hashtable中的每一项都有两个域,分别是关键字域 key 和值域 value(存储的对象)。Key 和 Value 都可以是任意的Object类型的对象,但不能为空。
    装填因子(Load Factor):装填因子表示为哈希表的装满程度,其值等于元素数比上哈希表的长度。

    哈希表的使用
    哈希表类主要有三种形式的构造方法:
    Hashtable();//默认构造函数,初始容量为101,最大填充因子0.75
    Hashtable(int capacity);
    Hashtable (int capacity,float loadFactor)
    哈希表类的主要方法如下:
    void clear() ——————————–重新设置并清空哈希表
    boolean contains(Object value) ——-确定哈希表内是否包含了给定的对象,若有返回true,否则false
    boolean containsKey(Object key) —–确定哈希表内是否包含了给定的关键字,若有返回true,否则false
    boolean isEmpty() ————————-确认哈希表是否为空,若是返回true,否则false
    Object get(Object key) —————获取对应关键字的对象,若不存在返回null
    void rehash() ——–再哈希,扩充哈希表使之可以保存更多的元素,当哈希表达到饱和时,系统自动调用此方法
    Object put(Object key, Object value)-用给定的关键字把对象保存到哈希表中,此处的关键字和元素均不为空
    remove(Object key) ——————-从哈希表中删除与给定关键字相对应的对象,若该对象不存在返回null
    int size() ——————————返回哈希表的大小
    String toString() ———————–将哈希表内容转换为字符串
    哈希表的创建也可以通过new操作符实现。其语句为:HashTable has = new HashTable();
    例如:

    import java.util.*;
    class eg1{
    public static void main(String args[]){
    Hashtable has = new Hashtable();
    has.put("one", new Integer(1));
    has.put("two", new Integer(2));
    has.put("three", new Integer(3));
    has.put("four", new Double(12.3));
    Set s = has.keySet();
    for(Iterator i = s.iterator(); i.hasNext();){
    System.out.println(has.get(i.next()));
    }
    }
    }

    运行结果
    2
    1
    3
    12.3

    展开全文
  • 1.创建哈希表 创建哈希表有两种方式:数组;HashMap //数组,索引作为key值 String[] hashTable = new String[4]; //HashMap HashMap<Integer,String> map = new HashMap<>(); 2.添加元素 //数组 ...

    1.创建哈希表

    • 创建哈希表有两种方式:数组;HashMap
    //数组,索引作为key值
    String[] hashTable = new String[4];
    
    //HashMap
    HashMap<Integer,String> map = new HashMap<>();
    

    2.添加元素

    //数组
    hashTable[1] = "hanmeimei";
    hashTable[2] = "lihua";
    hashTable[3] = "siyangyuan";
    
    //HashMap
    map.put(1,"hanmeimei");
    map.put(2,"lihua");
    map.put(3,"siyangyuan");
    

    3.更新元素

    //数组
    hashTable[1] = "bishi";
    
    //HashMap
    map.put(1,"bishi");
    

    4.删除元素

    //数组,将对应的key的值改为不常用的值
    hashTable[1] = "";
    
    //HashMap
    map.remove(1);
    

    5.获取元素

    //数组
    String temp = hashTable[3];
    
    //HashMap
    map.get(3);
    

    6.检查key存在?

    //数组,不好找
    
    //HashMap,返回ture or false
    map.containsKey(3);
    

    7.长度,是否还有元素

    //HashMap,长度
    map.size();
    
    //HashMap,是否还有元素
    map.isEmpty();
    
    展开全文
  • Java哈希表及链式哈希表的实现

    千次阅读 2019-06-18 14:40:02
    哈希表也称为散列表,是用来存储群体对象的集合类结构。 什么是哈希表 数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种...

    哈希表也称为散列表,是用来存储群体对象的集合类结构。

    什么是哈希表

    数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种顺序(如顺序查找或二分查找)与各个元素进行比较,当数组或向量中的元素数量很多时,查找的效率会明显的降低。

    一种有效的存储方式,是不与其他元素进行比较,一次存取便能得到所需要的记录。这就需要在对象的存储位置和对象的关键属性(设为 k)之间建立一个特定的对应关系(设为 f),使每个对象与一个唯一的存储位置相对应。在查找时,只要根据待查对象的关键属性 k 计算f(k)的值即可。如果此对象在集合中,则必定在存储位置 f(k)上,因此不需要与集合中的其他元素进行比较。称这种对应关系 f 为哈希(hash)方法,按照这种思想建立的表为哈希表。

    Java 使用哈希表类(Hashtable)来实现哈希表,以下是与哈希表相关的一些概念:

    • 容量(Capacity):Hashtable 的容量不是固定的,随对象的加入其容量也可以自动增长。

    • 关键字(Key):每个存储的对象都需要有一个关键字,key 可以是对象本身,也可以是对象的一部分(如某个属性)。要求在一个 Hashtable 中的所有关键字都是唯一的。

    • 哈希码(Hash Code):若要将对象存储到 Hashtable 上,就需要将其关键字 key 映射到一个整型数据,成为 key 的哈希码。

    • 项(Item):Hashtable 中的每一项都有两个域,分别是关键字域 key 和值域 value(存储的对象)。Key 和 value 都可以是任意的 Object 类型的对象,但不能为空。

    • 装填因子(Load Factor):装填因子表示为哈希表的装满程度,其值等于元素数比上哈希表的长度。

    链式哈希表的描述

    链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个“桶”,我们将所有的元素通过散列的方式放到具体的不同的桶中。插入元素时,首先将其键传入一个哈希函数(该过程称为哈希键),函数通过散列的方式告知元素属于哪个“桶”,然后在相应的链表头插入元素。查找或删除元素时,用同们的方式先找到元素的“桶”,然后遍历相应的链表,直到发现我们想要的元素。因为每个“桶”都是一个链表,所以链式哈希表并不限制包含元素的个数。然而,如果表变得太大,它的性能将会降低。

    冲突问题:两个不同的键映射到同一个位置

    链式哈希表的实现

    链式哈希表的操作与属性有:初始化、添加元素、删除元素、查找key值、获取哈希表中key值的个数。
    链式哈希表的实现

    /**
     * 描述: 实现链式哈希表结构
     *
     * 哈希函数:除留余数  data % bucket_size =
     * 扩容的时候,按原来空间大小的2倍+1扩容就可以
     *
     */
    public class LinkHashTable<K extends Comparable<K>,V> {
    
        // 哈希桶
        private Entry<K,V>[] table;
        // 装载因子 0.75
        private double loadFactor;
        // 记录已经占用的桶的数量
        private int usedBucketSize;
    
        /**
         * 哈希表初始化
         */
        public LinkHashTable(){
            this.table = new Entry[3];
            this.loadFactor = 0.75;
            this.usedBucketSize = 0;
        }
    
        /**
         * 给哈希表增加元素
         * @param key
         * @param value
         */
        public void put(K key, V value){
            double lf = usedBucketSize*1.0 / this.table.length;
            if(lf > this.loadFactor){
                expand();
            }
    
            int idx = key.hashCode() % this.table.length;
            if(this.table[idx] == null){
                 // 桶为空
                this.table[idx] = new Entry<>(key, value, null);
                this.usedBucketSize++;
            } else {
                // 桶已经有元素, 防止key被重复插入
                Entry<K,V> cur = this.table[idx];
                while(cur != null){
                    if(cur.key.compareTo(key) == 0){
                        // key值已经存在
                        cur.value = value;
                        break;
                    }
                    cur = cur.next;
                }
    
                // cur == null表示上面的while循环没有找见key值相等的节点
                if(cur == null){
                    this.table[idx] = new Entry<>(key, value, this.table[idx]);
                }
            }
        }
    
        /**
         * 在哈希表中查询key是否存在,如果key存在,返回它对应的value值,
         * 否则返回null
         * @param key
         * @return
         */
        public V get(K key){
            int idx = key.hashCode() % this.table.length;
            if(this.table[idx] == null){
                return null;
            } else{
                Entry<K,V> cur = this.table[idx];
                while(cur != null){
                    if(cur.key.compareTo(key) == 0){
                        return cur.value;
                    }
                    cur = cur.next;
                }
                return null;
            }
        }
    
        /**
         * 删除哈希表中key值为参数指定的节点
         * @param key
         */
        public void remove(K key){
            int idx = key.hashCode() % this.table.length;
            if(this.table[idx] == null){
                return;
            } else {
                /**
                 * 桶不为空,需要遍历桶中的链表节点
                 */
                Entry<K,V> pre = null;
                Entry<K,V> cur = this.table[idx];
                while(cur != null){
                    if(cur.key.compareTo(key) == 0){
                        if(pre == null){
                            // 删除的是桶中的第一个节点
                            this.table[idx] = cur.next;
                        } else {
                            // 删除的不是桶中的第一个节点
                            pre.next = cur.next;
                        }
    
                        // 桶的元素被删除完了
                        if(this.table[idx] == null){
                            this.usedBucketSize--;
                        }
                        return;
                    }
                    pre = cur;
                    cur = cur.next;
                }
            }
        }
    
        /**
         * 哈希表的扩容函数
         */
        private void expand(){
            Entry<K,V>[] oldTable = this.table;
            this.usedBucketSize = 0;
            this.table = new Entry[2*oldTable.length];
    
            for (int i = 0; i < oldTable.length; i++) {
                Entry<K,V> cur = oldTable[i];
                while(cur != null){
                    this.put(cur.key, cur.value);
                    cur = cur.next;
                }
            }
        }
    
        /**
         * 链式哈希表中节点的类型
         * @param <K,V>
         */
        static class Entry<K extends Comparable<K>,V>{
            K key;  // student id
            V value; // student
            Entry<K,V> next;
    
            public Entry(K key, V value, Entry<K, V> next) {
                this.key = key;
                this.value = value;
                this.next = next;
            }
        }
    
        public static void main(String[] args) {
            LinkHashTable<Integer, String> ht
                    = new LinkHashTable<>();
            /*ht.put(100, "张宇");
            ht.put(103, "张璐");
            ht.put(105, "冯超");
    
            System.out.println(ht.get(104));*/
    
            Random rd = new Random();
            int[] arr = new int[1000000];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = rd.nextInt(60000);
            }
    
            // key: 数字   值:数字出现的次数
            LinkHashTable<Integer, Integer> ht1
                    = new LinkHashTable<>();
            for (int i = 0; i < arr.length; i++) { // O(n)
                Integer val = ht1.get(arr[i]); // O(1)
                if(val == null){
                    ht1.put(arr[i], 1);
                } else {
                    ht1.put(arr[i], val+1); // O(1)
                }
            }
        }
    
    
    展开全文
  • [Java]Java哈希表之HashMap的常见用法和原理

    Java中哈希表之HashMap的常见用法及原理

    (参考:https://blog.csdn.net/visant/article/details/80045154 )

    一、HashMap介绍

    基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。

    二、HashMap原理

    1. 存储原理

    可以看作是数组和链表结合组成的复合结构,数组被分为一个个桶(bucket),每个桶存储有一个或多个Entry对象(每个Entry对象包含三部分key、value,next),通过哈希值决定了Entry对象(键值对)在这个数组的寻址;哈希值相同的Entry对象(键值对),则以链表形式存储。如果链表大小超过树形转换的阈值(TREEIFY_THRESHOLD= 8),链表就会被改造为树形结构。
    例如: 第一个键值对A进来。通过计算其key的hash得到的index=0。记做:Entry[0] = A。
    第二个键值对B,通过计算其index也等于0, HashMap会将B.next =A,Entry[0] =B,
    第三个键值对 C,index也等于0,那么C.next = B,Entry[0] = C;
    这样我们发现index=0的地方事实上存取了A,B,C三个键值对,它们通过next这个属性链接在一起。 对于不同的元素,可能计算出了相同的函数值,这样就产生了“冲突”,这就需要解决冲突,“直接定址”与“解决冲突”是哈希表的两大特点。

    2. 工作原理

    HashMap的工作原理 :HashMap是基于散列法(又称哈希法)的原理,使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket(桶)位置来储存Entry对象。HashMap是在bucket中储存键对象和值对象,作为Map.Entry,并不是仅仅只在bucket中存储值。

    3. 存取过程

    3.1 put键值对存数据

    在这里插入图片描述

    • ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;
    • ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;
    • ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;
    • ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;
    • ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
    • ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

    3.1 get获取值

    • ① 指定key 通过hash函数得到key的hash值 int hash=key.hashCode();
    • ② 调用内部方法getNode(),得到桶号(一般为hash值对桶数求模) int index = hash%Entry[].length;jdk1.6版本后使用位运算替代模运算,int index=hash&( Entry[].length - 1)
    • ③ 比较桶的内部元素是否与key相等,若都不相等,则没有找到。相等,则取出相等记录的value。
    • ④ 如果得到 key所在的桶的头结点恰好是红黑树节点,就调用红黑树节点的 getTreeNode() 方法,否则就遍历链表节点。getTreeNode方法使通过调用树形节点的 find()方法进行查找。由于之前添加时已经保证这个树是有序的,因此查找时基本就是折半查找,效率很高。
    • ⑤ 如果对比节点的哈希值和要查找的哈希值相等,就会判断 key 是否相等,相等就直接返回;不相等就从子树中递归查找。

    4. 查询时间复杂度

    HashMap的本质可以认为是一个数组,数组的每个索引被称为桶,每个桶里放着一个单链表,一个节点连着一个节点。很明显通过下标来检索数组元素时间复杂度为O(1),而且遍历链表的时间复杂度是O(n),所以在链表长度尽可能短的前提下,HashMap的查询复杂度接近O(1)

    三、HashMap使用方法

    1. 构造方法摘要

    • HashMap():构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
    • HashMap(int initialCapacity):构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
    • HashMap(int initialCapacity, float loadFactor):构造一个带指定初始容量和加载因子的空 HashMap。
    • HashMap(Map<? extends K,? extends V> m):构造一个映射关系与指定 Map 相同的 HashMap。

    2. 方法摘要

    • void clear():从此映射中移除所有映射关系。
    • Object clone():返回此 HashMap实例的浅表复制:并不克隆键和值本身。
    • boolean containsKey(Object key):如果此映射包含对于指定的键的映射关系,则返回 true。
    • boolean containsValue(Object value): 如果此映射将一个或多个键映射到指定值,则返回 true。
    • Set<Map.Entry<K,V>> entrySet():返回此映射所包含的映射关系的 collection 视图。 V get(Object key):返回指定键在此标识哈希映射中所映射的值,如果对于此键来说,映射不包含任何映射关系,则返回 null。
    • boolean isEmpty():如果此映射不包含键-值映射关系,则返回 true。 Set keySet():返回此映射中所包含的键的set 视图。
    • V put(K key, V value): 在此映射中关联指定值与指定键。
    • void putAll(Map<?extends K,? extends V>m):将指定映射的所有映射关系复制到此映射中,这些映射关系将替换此映射目前针对指定映射的所有键的所有映射关系。
    • V remove(Object key): 如果此映射中存在该键的映射关系,则将其删除。
    • int size():返回此映射中的键-值映射关系数。
    • Collection values():返回此映射所包含的值的collection 视图。

    3. 排序

    3.1 HashMap按Value排序

    /* HashMap按Value排序 */
       public static List<Map.Entry<String, Integer>> mapValueSort(HashMap<String, Integer> labelsMap) {
           List<Map.Entry<String, Integer>> list = new ArrayList<>(labelsMap.entrySet());
           list.sort(new Comparator<Map.Entry<String, Integer>>() {
               public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                   /* compare返回值为三种:(A为前者,B为后者)
                   * -1:A<B
                   * 0:A=B
                   * 1:A>B
                   * */
                   return o1.getValue() < o2.getValue() ? 1 : ((o1.getValue() == o2.getValue()) ? 0 : -1);
               }
           });
           for (Map.Entry<String, Integer> mapping : list) {
               System.out.println(mapping.getKey() + ":" + mapping.getValue());
           }
           return list;
       }
    

    3.2 HashMap按Value排序

        /* HashMap按Value排序 */
        public static List<Map.Entry<String, Integer>> mapKeySort(HashMap<String, Integer> labelsMap) {
            List<Map.Entry<String, Integer>> list = new ArrayList<>(labelsMap.entrySet());
            list.sort(new Comparator<Map.Entry<String, Integer>>() {
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                    /* compareTo返回值:
                       如果此字符串小于字符串参数,则返回一个小于 0 的值
                       如果参数字符串等于此字符串,则返回值 0
                       如果此字符串大于字符串参数,则返回一个大于 0 的值*/
                    return o1.getKey().compareTo(o2.getKey());
                }
            });
            for (Map.Entry<String, Integer> mapping : list) {
                System.out.println(mapping.getKey() + ":" + mapping.getValue());
            }
            return list;
        }
    

    3.3 HashMap按Value排序 如果Value相同按Key的字典序排序

        /* HashMap按Value排序 如果Value相同按Key的字典序排序 */
        public static List<Map.Entry<String, Integer>> mapKeyAndValueSort(HashMap<String, Integer> labelsMap) {
            List<Map.Entry<String, Integer>> list = new ArrayList<>(labelsMap.entrySet());
            list.sort(new Comparator<Map.Entry<String, Integer>>() {
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                    /* compareTo返回值:
                       如果此字符串小于字符串参数,则返回一个小于 0 的值
                       如果参数字符串等于此字符串,则返回值 0
                       如果此字符串大于字符串参数,则返回一个大于 0 的值*/
                    if(o1.getValue() == o2.getValue()){
                        return o1.getKey().compareTo(o2.getKey());
                    }else{
                        return o2.getValue().compareTo(o1.getValue());
                    }
                }
            });
            for (Map.Entry<String, Integer> mapping : list) {
                System.out.println(mapping.getKey() + ":" + mapping.getValue());
            }
            return list;
        }
    

    4.输出

    HashMap<String, Integer> maps = new HashMap<>();
    

    4.1 entrySet() 返回此映射中包含的映射关系的set视图

    		/* 遍历Map */
            for (Map.Entry<String, Integer> mapping : maps.entrySet()) {
                System.out.println(mapping.getKey() + ":" + mapping.getValue());
            }
    

    4.2 获取指定key对应的value

    		System.out.println(maps.get("2"));
    

    4.3 maps.keySet()

            //得到map的key的集合
            Set<String> keySet = maps.keySet();
            //得到map的key的集合后,循环的根据key去取value就好了
            for (String key : keySet) {
                Integer value = maps.get(key);
                System.out.println(key+":"+value);
            }
    

    四、其他说明

    1. 如何重新调整HashMap的大小,如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?

    HashMap的扩容阈值(threshold = capacity* loadFactor 容量范围是16~2的30次方),就是通过它和size进行比较来判断是否需要扩容。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组(jdk1.6,但不超过最大容量),来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

    2. 解决 hash 冲突的常见方法

    a. 链地址法:将哈希表的每个单元作为链表的头结点,所有哈希地址为 i 的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
    b. 开放定址法:即发生冲突时,去寻找下一个空的哈希地址。只要哈希表足够大,总能找到空的哈希地址。
    c. 再哈希法:即发生冲突时,由其他的函数再计算一次哈希值。
    d. 建立公共溢出区:将哈希表分为基本表和溢出表,发生冲突时,将冲突的元素放入溢出表。
    HashMap 就是使用链地址法来解决冲突的(jdk8中采用平衡树来替代链表存储冲突的元素,但hash() 方法原理相同)。当两个对象的hashcode相同时,它们的bucket位置相同,碰撞就会发生。此时,可以将 put 进来的 K- V 对象插入到链表的尾部。对于储存在同一个bucket位置的链表对象,可通过键对象的equals()方法用来找到键值对。

    3. 对比:Hashtable、HashMap、TreeMap

    Hashtable 是早期Java类库提供的一个哈希表实现,本身是同步的,不支持 null 键和值,由于同步导致的性能开销,所以已经很少被推荐使用。
    HashMap与 HashTable主要区别在于 HashMap 不是同步的,支持 null 键和值等。通常情况下,HashMap 进行 put 或者 get 操作,可以达到常数时间的性能,所以它是绝大部分利用键值对存取场景的首选。
    TreeMap 则是基于红黑树的一种提供顺序访问的 Map,和 HashMap 不同,它的 get、put、remove 之类操作都是 O(log(n))的时间复杂度,具体顺序可以由指定的 Comparator 来决定,或者根据键的自然顺序来判断。

    五、源码

    https://github.com/zhangzhishun/java/blob/master/src/untils/_Map.java

    展开全文
  • 文章目录Java哈希表概念冲突避免冲突哈希函数的设计方法常见哈希函数负载因子调节解决哈希冲突两种常见的方法是:闭散列和开散列哈希表和 java 类集的关系 Java哈希表 概念 顺序结构以及平衡树中,元素关键码与其...
  • Java哈希表实现

    2020-08-24 01:20:38
    哈希表 java实现
  • java哈希表及其应用详解

    万次阅读 多人点赞 2017-07-10 15:52:23
    什么是哈希表 数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种顺序(如顺序查找或二分查找)与各个元素进行比较,当数组或...
  • 哈希表Java中的使用 定义 对象的存储位置和对象的关健值之间存在某种对应关系。其定义同数据结构之中的定义。 在java中的使用 导包 import java.util.HashMap; 定义 HsahMap<Integer,Integer> hash = ...
  • java使用哈希表

    2017-04-20 17:45:33
    java使用哈希表 哈希表是一种重要的存储方式,也是一种常见的检索方法。其基本思想是将关系码的值作为自变量,通过一定的函数关系计算出对应的函数值,把这个数值解释为结点的存储地址,将结点存入计算得到存储...
  • JAVA哈希表的构建(拉链法)

    千次阅读 2018-07-15 19:21:02
    哈希表是一个用途很广泛的数据结构,常用于需要进行大集合搜索的地方,比如腾讯QQ。对于上线的用户我们需要将其添加到一个集合中,以便对其进行各种处理。那么这个集合该采取哪种数据结构呢?最基本的数据结构就两种...
  • Java哈希表

    2021-01-02 23:02:54
    理想的搜索方法:可以不经过比较就可以得到要搜索的元素。如果构造一种存储结构,通过某种函数(hashfunc)来使元素与存储位置之间能够建立一一映射的关系,那么在查找时通过该函数就可以很快的找到该元素。 元素...
  • Java世界里,HashMap是相当相当的重要,而和HashMap有关的哈希表是个什么东西? 百科解释: 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键...
  • Java 哈希表

    2020-08-11 18:13:24
    Java 哈希表概念冲突-概念冲突-避免冲突避免-哈希函数设计冲突避免-负载因子调节*冲突-解决闭散列开散列/哈希桶哈希冲突严重的解决办法实现性能分析和 java 类集的关系 概念 顺序结构以及平衡树中,元素关键码与其...
  • 哈希表的基本原理和实现方法Java)   散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这...
  • 哈希表 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放...
  • 实现哈希表有两个主要的问题, 一个是解决哈希函数的设计, 一个是哈希冲突的处理 哈希函数 键通过哈希函数可以得到一个索引, 通过索引可以在内存中找到这个键所包含的信息, 索引的分布越均匀冲突才越少 所有类型的...
  • 哈希表JAVA中如何实现

    千次阅读 2016-11-23 20:42:44
    为什么使用“与”操作,目的是为了将散列值高位全部归零,只保留低位,用于做哈希表地址(即数组下标)。如以哈希表长度16为例,16-1=15,二进制为表示为:00000000 00000000 00001111,与某散列值做“与”操作如下...
  • Java基本查找算法 -- 哈希表的查找

    千次阅读 2020-07-12 23:48:44
    一、哈希表的查找 前面讨论的线性表和树表的查找中,表中的相对位置是随机的,也就是是说,记录在表中的位置跟记录的关键字之间不存在确定关系。因此,在这些表中查找记录时需要进行一系列的关键字比较。这一类查找...
  • 哈希表的实现(Java实现)

    千次阅读 2019-10-26 12:36:06
    哈希表的结构是由数组+链表或者数组+二叉树组成,实现的思路是创建一个固定大小的链表数组,将各条链表交给数组来进行管理,根据自定义的规则,将数据依次插入链表中,这样查找起来会非常方便。 package ...
  • 一.概述 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构...使用哈希函数向数组插入数据后,这个数组就是哈希表。 哈希函数和散列值(哈希值),散列值(哈希值)就是把任意长...
  • 文章目录1、哈希表介绍2、哈希函数H(k)哈希函数的构造方法:(1)直接定址法(2)数字分析法(3)平方取中法(4)折叠法(5)除留余数法(6)随机数法3、解决哈希碰撞1、开放地址法2、链地址法(拉链法)4、实例:...
  • 哈希表java实现

    千次阅读 2017-01-17 16:36:58
    一、为什么要用哈希表 树的操作通常需要O(N)的时间级,而哈希表中无论存有多少数据,它的插入和查找(有时包括删除...而且目前没有一种简便的方法可以对哈希表进行有序(从大到小或者从小到大)的遍历,除非哈希表本身
  • 哈希表中的“表” 当我们需要存储一种映射数据时,就需要用到哈希表,也称为散列表(Hash Table)。 该数据结构中存储的是键(key)和值(value),它们是对应关系。 只需要给出一个指定的key,那么就能高效查找...
  • 哈希表Java中HashMap

    万次阅读 多人点赞 2016-08-05 01:24:46
    哈希表(Hash Table)是一种数据结构; 哈希函数,是支撑哈希表的一类函数; Map是映射、地图的意思,在Java中Map表示一种把K映射到V的数据类型; HashMap是Java中用哈希数据结构实现的Map; 一、Hash算法...
  • java数据结构——哈希表

    千次阅读 2018-10-13 09:42:53
    哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值...哈希表节点一般包括两个变量,key和data,其中key用来存储和查找,data表示存储的数据,使用java语言表述如下; pu...
  • javascript里面是没有哈希表的,一直在java,C#中有时候用到了这一种数据结构,javascript里面若没有,感觉非常不顺手。细细看来,其实javascript的object的属性其实与哈希表非常类似。 如: var person = {}; person[...
  • Java-哈希表、有序表的一些用法

    千次阅读 2019-02-05 20:42:38
    Java-哈希表、有序表的一些用法哈希表HashMap常见用法如何删除HashMap中指定值的元素HashSet各种用法有序表TreeMapTreeSet 哈希表 哈希表的操作时间复杂度都是O(1),与数据量无关,但常数时间很大。 基础类型:按值...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 119,998
精华内容 47,999
关键字:

java哈希表用法

java 订阅