cari
RumahJavajavaTutorialJava编程思想学习课时(四)第17章-容器深入探讨

1 Set和存储顺序

  • 加入Set的元素必须定义equals()方法以确保对象的唯一性

  • hashCode()只有这个类被置于HashSet或者LinkedHashSet中时才是必需的。但是对于良好的编程风格而言,你应该在覆盖equals()方法时,总是同时覆盖hashCode()方法。

  • 如果一个对象被用于任何种类的排序容器中,例如SortedSetTreeSet是其唯一实现),那么它必须实现Comparable接口。

  • 注意,SortedSet的意思是“按对象的比较函数对元素排序”,而不是指“元素插入的次序”。插入顺序LinkedHashSet来保存。

2 队列

  • 队了并发应用,Queue在Java SE5中仅有的两个实现是LinkiedListPriorityQueue,它们仅有排序行为的差异,性能上没有差异。

  • 优先级队列PriorityQueue的排列顺序也是通过实现Comparable而进行控制的。

3 Map

  映射表(也称为关联数组Associative Array)。

3.1 性能

  HashMap使用了特殊的值,称作散列码(hash code),来取代对键的缓慢搜索。散列码是“相对唯一”的、用以代表对象的int值,它是通过将该对象的某些信息进行转换而生成的。
hashCode()是根类Object中的方法,因此所有对象都能产生散列码。

  对Map中使用的键的要求与对Set中的元素的要求一样:

  • 任何键都必须具有一个equals()方法;

  • 如果键被用于散列Map,那么它必须还具有恰当的hashCode()方法;

  • 如果键被用于TreeMap,那么它必须实现Comparable

4 散列与散列码

  HashMap使用equals()判断当前的键是否与表中存在的键相同。
  默认的Object.equals()只是比较对象的地址如果要使用自己的类作为HashMap的键,必须同时重写hashCode()equals()
  正确的equals()方法必须满足下列5个条件:

  • 自反性。

  • 对称性。

  • 传递性。

  • 一致性。

  • 对任何不是null的xx.equals(null)一定返回false

4.1 散列概念

  使用散列的目的在于:想要使用一个对象来查找另一个对象
  Map的实现类使用散列是为了提高查询速度

散列的价值在于速度散列使得查询得以快速进行。由于瓶颈位于查询速度,因此解决方案之一就是保持键的排序状态,然后使用Collections.binarySearch()进行查询。

散列则更进一步,它将键保存在某处,以便能够很快找到。存储一组元素最快的数据结构是数组,所以用它来表示键的信息(请小心留意,我是说键的信息,而不是键本身)。但是因为数组不能调整容量,因此就有一个问题:我们希望在Map中保存数量不确定的值,但是如果键的数量被数组的容量限制了,该怎么办?

答案就是:数组并不保存键本身。而是通过键对象生成一个数字,将其作为数组的下标。这个数字就是散列码,由定义在Object中的、且可能由你的类覆盖的hashCode()方法(在计算机科学的术语中称为散列函数)生成。

为解决数组容量固定的问题,不同的键可以产生相同的下标。也就是说,可能会有冲突,即散列码不必是独一无二的。因此,数组多大就不重要了,任何键总能在数组中找到它的位置。

4.2 理解散列

  综上,散列就是将一个对象生成一个数字保存下来(作为数组的下标),然后在查找这个对象时直接找到这个数字就可以了,所以散列的目的是为了提高查找速度,而手段是将一个对象生成的数字与其关联并保存下来(通过数组,称为散列表)。这个生成的数字就是散列码。而生成这个散列码的方法称为散列函数hashCode())。

4.3 HashMap查询过程(快速原因)

  因此,HashMap中查询一个key的过程就是:

  • 首先计算散列码

  • 然后使用散列码查询数组(散列码作变数组下标)

  • 如果没有冲突,即生成这个散列码的对象只有一个,则散列码对应的数组下标的位置就是这个要查找的元素

  • 如果有冲突,则散列码对应的下标所在数组元素保存的是一个list,然后对list中的值使用equals()方法进行线性查询。

  因此,不是查询整个list,而是快速地跳到数组的某个位置,只对很少的元素进行比较。这便是HashMap会如此快速的原因

4.4 简单散列Map的实现

  • 散列表中的槽位(slot)通常称为桶位(bucket)

  • 为使散列均匀,桶的数量通常使用质数JDK5中是质数,JDK7中已经是2的整数次方了)。

    事实证明,质数实际上并不是散列桶的理想容量。近来,(通过广泛的测试)Java的散列函数都使用2的整数次方。对现代处理器来说,除法与求余数是最慢的操作。使用2的整数次方长度的散列表,可用掩码代替除法。因为get()是使用最多的操作,求余数的%操作是其开销最大的部分,而使用2的整数次方可以消除此开销(也可能对hashCode()有些影响)。
  • get()方法按照与put()方法相同的方式计算在buckets数组中的索引,这很重要,因为这样可以保证两个方法可以计算出相同的位置

package net.mrliuli.containers;

import java.util.*;public class SimpleHashMap<K, V> extends AbstractMap<K, V> {    // Choose a prime number for the hash table size, to achieve a uniform distribution:
    static final int SIZE = 997;    // You can&#39;t have a physical array of generics, but you can upcast to one:
    @SuppressWarnings("unchecked")
    LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[SIZE];

    @Override    public V put(K key, V value){        int index = Math.abs(key.hashCode()) % SIZE;        if(buckets[index] == null){
            buckets[index] = new LinkedList<MapEntry<K,V>>();
        }

        LinkedList<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);

        boolean found = false;
        V oldValue = null;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();        while(it.hasNext()){
            MapEntry<K,V> iPair = it.next();            if(iPair.equals(key)){
                oldValue = iPair.getValue();
                it.set(pair); // Replace old with new
                found = true;                break;
            }
        }        if(!found){
            buckets[index].add(pair);
        }        return oldValue;
    }

    @Override    public V get(Object key){        int index = Math.abs(key.hashCode()) % SIZE;        if(buckets[index] == null) return null;        for(MapEntry<K,V> iPair : buckets[index]){            if(iPair.getKey().equals(key)){                return iPair.getValue();
            }
        }        return null;
    }

    @Override    public Set<Map.Entry<K,V>> entrySet(){
        Set<Map.Entry<K,V>> set = new HashSet<Map.Entry<K, V>>();        for(LinkedList<MapEntry<K,V>> bucket : buckets){            if(bucket == null) continue;            for(MapEntry<K,V> mpair : bucket){                set.add(mpair);
            }
        }        return set;
    }    public static void main(String[] args){
        SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();        for(String s : "to be or not to be is a question".split(" ")){
            m.put(s, s);
            System.out.println(m);
        }
        System.out.println(m);
        System.out.println(m.get("be"));
        System.out.println(m.entrySet());
    }
}

4.5 覆盖hashCode()

  设计`hashCode()`时要考虑的因素:

  • 最重要的因素:无论何时,对同一相对象调用hashCode()都应该生成同样的值

  • 此外,不应该使hashCode()依赖于具有唯一性的对象信息,尤其是使用this的值,这只能产生很糟糕的hashCode()。因为这样做无法生成一个新的键,使之与put()中原始的键值对中的键相同。即应该使用对象内有意义的识别信息。也就是说,它必须基于对象的内容生成散列码。

  • 但是,通过hashCode() equals()必须能够完全确定对象的身份。

  • 因为在生成桶的下标前,hashCode()还需要进一步处理,所以散列码的生成范围并不重要,只要是int即可。

  • 好的hashCode()应该产生分布均匀的散列码。

《Effective Java™ Programming Language Guide (Addison-Wesley, 2001)》为怎样写出一个像样的hashCode()给出了一个基本的指导:

  1. int变量result赋予一个非零值常量,如17

  2. 为对象内每个有意义的域f(即每个可以做equals()操作的域)计算出一个int散列码c

域类型 计算
boolean c=(f?0:1)
byte、char、short或int c=(int)f
long c=(int)(f^(f>>>32))
float c=Float.floatToIntBits(f);
double long l = Double.doubleToLongBits(f);
Object,其equals()调用这个域的equals() c=f.hashCode()
数组 对每个元素应用上述规则

3. 合并计算散列码:result = 37 * result + c;
4. 返回result。
5. 检查hashCode()最后生成的结果,确保相同的对象有相同的散列码。

5 选择不同接口的实现

5.1 微基准测试的危险(Microbenchmarking dangers)

已证明0.0是包含在Math.random()的输出中的,按照数学术语,即其范围是[0,1)

5.2 HashMap的性能因子

  HashMap中的一些术语:

  • 容量(Capacity):表中的桶位数(The number of buckets in the table)。

  • 初始容量(Initial capacity):表在创建时所拥有的桶位数。HashMapHashSet都具有允许你指定初始容量的构造器。

  • 尺寸(Size):表中当前存储的项数。

  • 负载因子(Loadfactor):尺寸/容量。空表的负载因子是0,而半满表的负载因子是0.5,依此类推。负载轻的表产生冲突的可能性小,因此对于插入和查找都是最理想的(但是会减慢使用迭代器进行遍历的过程)。HashMapHashSet都具有允许你指定负载因子的构造器,表示当负载情况达到该负载的水平时,容器将自动增加其容量(桶位数),实现方式是使容量大致加倍,并重新将现有对象分布到新的桶位集中(这被称为再散列)。

HashMap使用的默认负载因子是0.75(只有当表达到四分之三满时,才进行再散列),这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低表所需的空间,但会增加查找代价,这很重要,因为查找是我们在大多数时间里所做的操作(包括get()put())。

6 Collection或Map的同步控制

  Collections类有办法能够自动同步整个容器。其语法与“不可修改的”方法相似:

package net.mrliuli.containers;

import java.util.*;public class Synchronization {    public static void main(String[] args){
        Collection<String> c = Collections.synchronizedCollection(new ArrayList<String>());
        List<String> list = Collections.synchronizedList(new ArrayList<String>());        Set<String> s = Collections.synchronizedSet(new HashSet<String>());        Set<String> ss = Collections.synchronizedSortedSet(new TreeSet<String>());
        Map<String, String> m = Collections.synchronizedMap(new HashMap<String, String>());
        Map<String, String> sm = Collections.synchronizedSortedMap(new TreeMap<String, String>());
    }
}

6.1 快速报错(fail-fast)

  Java容器有一种保护机制能够防止多个进行同时修改同一个容器的内容。Java容器类类库采用快速报错(fail-fast)机制。它会探查容器上的任何除了你的进程所进行的操作以外的所有变化,一旦它发现其他进程修改了容器,就会立刻抛出ConcurrentModificationException异常。这就是“快速报错”的意思——即,不是使用复杂的算法在事后来检查问题。

package net.mrliuli.containers;
import java.util.*;public class FailFast {    public static void main(String[] args){
        Collection<String> c = new ArrayList<>();
        Iterator<String> it = c.iterator();
        c.add("An Object");        try{
            String s = it.next();
        }catch(ConcurrentModificationException e){
            System.out.println(e);
        }
    }
}

相关文章:

Java编程思想学习课时(三)第15章-泛型

Java编程思想学习课时(五)第18章-Java IO系统

Atas ialah kandungan terperinci Java编程思想学习课时(四)第17章-容器深入探讨. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
带你搞懂Java结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

java中封装是什么java中封装是什么May 16, 2019 pm 06:08 PM

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

归纳整理JAVA装饰器模式(实例详解)归纳整理JAVA装饰器模式(实例详解)May 05, 2022 pm 06:48 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。

See all articles

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Alat panas

Pelayar Peperiksaan Selamat

Pelayar Peperiksaan Selamat

Pelayar Peperiksaan Selamat ialah persekitaran pelayar selamat untuk mengambil peperiksaan dalam talian dengan selamat. Perisian ini menukar mana-mana komputer menjadi stesen kerja yang selamat. Ia mengawal akses kepada mana-mana utiliti dan menghalang pelajar daripada menggunakan sumber yang tidak dibenarkan.

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Persekitaran pembangunan bersepadu PHP yang berkuasa

SublimeText3 versi Inggeris

SublimeText3 versi Inggeris

Disyorkan: Versi Win, menyokong gesaan kod!

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual