上杭网站,佛山专业做网站的公司,小程序源码网免费,网站和服务器是什么关系一、java中的容器 集合主要分为Collection和Map两大接口#xff1b;Collection集合的子接口有List、Set#xff1b;List集合的实现类有ArrayList底层是数组、LinkedList底层是双向非循环列表、Vector#xff1b;Set集合的实现类有HashSet、TreeSet#xff1b;Map集合的实现…一、java中的容器 集合主要分为Collection和Map两大接口Collection集合的子接口有List、SetList集合的实现类有ArrayList底层是数组、LinkedList底层是双向非循环列表、VectorSet集合的实现类有HashSet、TreeSetMap集合的实现类有HashMap、TreeMap、HashTable
(补充HashTable与HashMap类似线程安全子接口有Properties接口线程安全)
1.HashMap底层原理 HashMap是以键值对形式存储数据的底层由散列表组成jdk1.8之前是数组链表jdk1.8之后数组链表红黑树组成。 默认数组长度16 当添加元素时链表的长度大于等于8数组的长度小于64将数组长度扩容原数组长度的2倍当链表的长度大于等于8并且数组的长度大于等于64时将链表转为红黑树。红黑树是平衡二叉搜索树效率高。 当删除元素时链表长度小于7将红黑树转为链表。 补充jdk1.8之前头插法jdk1.8及之后尾插法1.7创建map时默认容量161.8创建map时默认无容量添加后为初始化长度为16 Hash冲突链地址法、开放地址法再次hash法建立公共溢出区
2.ArrayList、LinkedList、Vector集合的区别
ArrayList集合的底层是数组适用于集合的遍历和随机访问某个元素的场景添加元素时每次扩容为原数组长度的1.5倍。(长度默认0调用add方法后没有指定长度为10)
LinkedList集合的底层是双向非循环链表中间插入和删除元素效率比较高遍历效率比较低。
Vector集合与ArrayList类似底层也是数组线程是安全的每个方法都由synchronized修饰执行效率较低。(每次扩容为原数组长度2倍)
补充线程安全可以使用juc提供的集合CopyOnWriteArrayList写时复制
二、为什么 HashMap 的加载因子是0.75
为什么HashMap需要加载因子 解决冲突有什么方法 1.开放定址法 2.再哈希法 3.建立一个公共溢出区 4.链地址法拉链法 为什么HashMap加载因子一定是0.75而不是0.80.6 那么为什么不可以是0.8或者0.6呢 HashMap的底层是哈希表是存储键值对的结构类型它需要通过一定的计算才可以确定数据在哈希表中的存储位置
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}
// AbstractMap
public int hashCode() {int h 0;IteratorEntryK,V i entrySet().iterator();while (i.hasNext())h i.next().hashCode();return h;
} 一般的数据结构不是查询快就是插入快HashMap就是一个插入慢、查询快的数据结构。 但这种数据结构容易产生两种问题 ① 如果空间利用率高那么经过的哈希算法计算存储位置的时候会发现很多存储位置已经有数据了哈希冲突 ② 如果为了避免发生哈希冲突增大数组容量就会导致空间利用率不高。
而加载因子表示Hash表中元素的填满程度。
1. 加载因子
加载因子 填入表中的元素个数 / 散列表的长度
加载因子越大填满的元素越多空间利用率越高但发生冲突的机会变大了
加载因子越小填满的元素越少冲突发生的机会减小但空间浪费了更多了而且还会提高扩容rehash操作的次数。
冲突的机会越大说明需要查找的数据还需要通过另一个途径查找这样查找的成本就越高。因此必须在“冲突的机会”与“空间利用率”之间寻找一种平衡与折衷。
所以我们也能知道影响查找效率的因素主要有这几种 散列函数是否可以将哈希表中的数据均匀地散列 怎么处理冲突 哈希表的加载因子怎么选择
2. 解决冲突有什么方法
1. 开放定址法
Hi (H(key) di) MOD m其中i1,2,…,k(km-1) H(key)为哈希函数m为哈希表表长di为增量序列i为已发生冲突的次数。其中开放定址法根据步长不同可以分为3种
1.1 线性探查法Linear Probingdi 1,2,3,…,m-1
简单地说就是以当前冲突位置为起点步长为1循环查找直到找到一个空的位置如果循环完了都占不到位置就说明容器已经满了。举个栗子就像你在饭点去街上吃饭挨家去看是否有位置一样。
1.2 平方探测法Quadratic Probingdi ±12, ±22±32…±k2k≤m/2
相对于线性探查法这就相当于的步长为di i2来循环查找直到找到空的位置。以上面那个例子来看现在你不是挨家去看有没有位置了而是拿手机算去第i2家店然后去问这家店有没有位置。
1.3 伪随机探测法di 伪随机数序列
这个就是取随机数来作为步长。还是用上面的例子这次就是完全按心情去选一家店问有没有位置了。
但开放定址法有这些缺点 这种方法建立起来的哈希表当冲突多的时候数据容易堆集在一起这时候对查找不友好 删除结点的时候不能简单将结点的空间置空否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点只能在被删结点上添加删除标记而不能真正删除结点 如果哈希表的空间已经满了还需要建立一个溢出表来存入多出来的元素。
2. 再哈希法
Hi RHi(key), 其中i1,2,…,k RHi()函数是不同于H()的哈希函数用于同义词发生地址冲突时计算出另一个哈希函数地址直到不发生冲突位置。这种方法不容易产生堆集但是会增加计算时间。
所以再哈希法的缺点是增加了计算时间。
3. 建立一个公共溢出区 假设哈希函数的值域为[0, m-1]设向量HashTable[0,…,m-1]为基本表每个分量存放一个记录另外还设置了向量OverTable[0,…,v]为溢出表。基本表中存储的是关键字的记录一旦发生冲突不管他们哈希函数得到的哈希地址是什么都填入溢出表。 但这个方法的缺点在于查找冲突数据的时候需要遍历溢出表才能得到数据。
4. 链地址法拉链法
将冲突位置的元素构造成链表。在添加数据的时候如果哈希地址与哈希表上的元素冲突就放在这个位置的链表上。
拉链法的优点 处理冲突的方式简单且无堆集现象非同义词绝不会发生冲突因此平均查找长度较短 由于拉链法中各链表上的结点空间是动态申请的所以它更适合造表前无法确定表长的情况 删除结点操作易于实现只要简单地删除链表上的相应的结点即可。
拉链法的缺点需要额外的存储空间。
从HashMap的底层结构中我们可以看到HashMap采用是数组链表/红黑树的组合来作为底层结构也就是开放地址法链地址法的方式来实现HashMap。 3. 为什么HashMap加载因子一定是0.75而不是0.80.6 HashMap的底层其实也是哈希表散列表而解决冲突的方式是链地址法。HashMap的初始容量大小默认是16为了减少冲突发生的概率当HashMap的数组长度到达一个临界值的时候就会触发扩容把所有元素rehash之后再放在扩容后的容器中这是一个相当耗时的操作。
而这个临界值就是由加载因子和当前容器的容量大小来确定的
临界值 DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR
即默认情况下是16x0.7512时就会触发扩容操作。
那么为什么选择了0.75作为HashMap的加载因子呢这个跟一个统计学里很重要的原理——泊松分布有关。 泊松分布是统计学和概率学常见的离散概率分布适用于描述单位时间内随机事件发生的次数的概率分布。有兴趣推荐维基百科或者阮一峰老师的这篇文章泊松分布和指数分布 等号的左边P 表示概率N表示某种函数关系t 表示时间n 表示数量。等号的右边λ 表示事件的频率。 在HashMap的源码中有这么一段注释
* Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million 理想情况下使用随机哈希码在扩容阈值加载因子为0.75的情况下节点出现在频率在Hash桶表中遵循参数平均为0.5的泊松分布。忽略方差即X λtP(λt k)其中λt 0.5的情况按公式 计算结果如上述的列表所示当一个bin中的链表长度达到8个元素的时候概率为0.00000006几乎是一个不可能事件。 所以其实常数0.5是作为参数代入泊松分布来计算的而加载因子0.75是作为一个条件当HashMap长度为length/size ≥ 0.75时就扩容在这个条件下冲突后的拉链长度和概率结果为
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
4.为什么不可以是0.8或者0.6呢
HashMap中除了哈希算法之外有两个参数影响了性能初始容量和加载因子。初始容量是哈希表在创建时的容量加载因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。
5. 在维基百科来描述加载因子 对于开放定址法加载因子是特别重要因素应严格限制在0.7-0.8以下。超过0.8查表时的CPU缓存不命中cache missing按照指数曲线上升。因此一些采用开放定址法的hash库如Java的系统库限制了加载因子为0.75超过此值将resize散列表。 在设置初始容量时应该考虑到映射中所需的条目数及其加载因子以便最大限度地减少扩容rehash操作次数所以一般在使用HashMap时建议根据预估值设置初始容量以便减少扩容操作。 选择0.75作为默认的加载因子完全是时间和空间成本上寻求的一种折衷选择。
