哈希冲突、散列表学习记录

 1/********************************************
 2 * All Rights Reserved By www.laughing.ren
 3 * @author:Laughing_Lz
 4 * @version:2018年11月27日 上午1:07:01
 5 * ******************************************/
 6package ren.laughing.code.Test;
 7
 8import java.util.HashMap;
 9import java.util.LinkedHashMap;
10import java.util.Map;
11import java.util.TreeMap;
12
13public class Hash {
14    class Son {
15        private int age;
16        private String name;
17    }
18
19    /*
20     * ThreadLocalMap 使用了开放寻址法处理hash冲突 数据量小,装载因子小(较于链表更浪费内存空间)
21     * 开放寻址法的数据都存储在数组中,可以有效利用CPU缓存加快查询,而且序列化较为简单。
22     * 删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据。而且,在开放寻址法中,所有的数据都存储在一个数组中,比起链表法来说,冲突的代价更高。所以,
23     * 使用开放寻址法解决冲突的散列表,装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
24     */
25    public static void hash() {
26        // ThreadLocalMap是ThreadLocal的内部类,它是一个Map,key是ThreadLocal的实例变量
27        ThreadLocal<Son> threadLocal = new ThreadLocal<Son>();
28        // 使用链表法解决hash冲突,适用于大对象,大数据量,装载因子可以大于1,使用灵活,可将链表转换为红黑树、跳表等结构。
29        LinkedHashMap<String, Son> linkedHashMap = new LinkedHashMap<>();
30        HashMap<String, Son> map = new HashMap<String, Son>();
31        // hashmap 可修改初始大小,默认为16,装载因子默认0.75
32        HashMap<ObjectObject> hashMap = new HashMap<ObjectObject>(110);
33    }
34    /*
35     * 设计工业级的散列表,应具有哪些属性? 1.支持快速查询、插入、删除 2.内存占用合理,不能浪费过多的内存空间
36     * 3.性能稳定,极端情况下,散列表的性能也不会退化到无法接受的情况
37     */
38
39    /*
40     * 如何设计工业级的散列表? 1.设计一个合理的散列函数 2.定义装载因子阈值,并且设计动态扩容策略 3.选择合适的散列冲突解决方法
41     */
42
43    /*
44     * 集合类的带hash的,例如hashmap、hashset、hashtable等。
45     * hashmap中散列函数是key的hashcode与key的hashcode右移16位异或,这是为了把key的高位考虑进去,如果key是0,hash值为0
46     * 。在put的时候,如果表没有初始化,需要初始化下,在计算key的位置的时候很巧妙,使用表的length-1和key的hash值与计算的,
47     * 实际上就是对key的hash值对表长取模,基于hashmap是2的幂次方特性,这种位运算速度更快。如果put后hashmap的数据容量超过了表的容量*
48     * 负载因子,就会自动扩容,默认是两倍,自动扩容方法是将key的hash与表长直接与判断是否有高位,有高位就把这个node放到新表里旧表对应位置加旧表长的地方
49     * 。没有高位就直接是新表旧位置。这是hashmap1.8的处理方法。hashmap1.7还是对key的hash取模。如果是个非常大的数,赋值为integer
50     * .max。hashmap采用的是链地址法结合红黑树解决hash冲突,当桶中链表长度大于8就会将桶中数据结构转化为红黑树。
51     * hashtable默认的初使容量11,负载因子也是0.75,如果要指定初始化hashtable容量最好是给一个素数。
52     * 这是因为放入table的时候需要对表长取模,尽量分散地映射。hashtable通过链地址法解决hash冲突,当数据容量大于数据容量*负载因子自动扩容,
53     * 扩容原表长两倍+1。
54     */
55    /*
56     * TreeMap 使用红黑树的数据结构,好好研究源码
57     */
58    Map<StringString> map = new TreeMap<>();
59}

发表评论

电子邮件地址不会被公开。 必填项已用*标注