登录  /  注册
首页 > Java > java教程 > 正文

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

php是最好的语言
发布: 2018-08-09 14:42:15
原创
1285人浏览过

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

域类型计算
booleanc=(f?0:1)
byte、char、short或intc=(int)f
longc=(int)(f^(f>>>32))
floatc=Float.floatToIntBits(f);
doublelong 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系统

以上就是Java编程思想学习课时(四)第17章-容器深入探讨的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号