全教育培训行业第三方平台平台就业机构
扫码试听
扫码试听
Q:2638333071
首页 > 零基础学习 > 软件开发 > > 1000个哈希桶存50个元素不重复的概率
行业动态 行业问答 课程问答 零基础学习 就业前景 技术干货

1000个哈希桶存50个元素不重复的概率

发布时间:4 周 前 栏目:软件开发 浏览:

1、1000个哈希桶存50个元素不重复的概率

0.02。HashMap 中数组的每一个元素又称为哈希桶。根据数据显示,概率为0.02。现代数学集合论中,元素是组成集的每个对象。

1000个哈希桶存50个元素不重复的概率

2、hashmap和concurrenthashmap的区别是什么

hashmap和concurrenthashmap的区别如下:

HashMap不是线程安全的,而ConcurrentHashMap是线程安全的。

ConcurrentHashMap采用锁分段技术,将整个Hash桶进行了分段segment,也就是将这个大的数组分成了几个小的片段segment,而且每个小的片段segment上面都有锁存在。

那么在插入元素的时候就需要先找到应该插入到哪一个片段segment,然后再在这个片段上面进行插入,而且这里还需要获取segment锁。

ConcurrentHashMap让锁的粒度更精细一些,并发性能更好。

HashMap:

底层数组+链表实现,可以存储null键和null值,线程不安全。

初始size为16,扩容:newsize = oldsize*2,size一定为2的n次幂。

扩容针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入。

插入元素后才判断该不该扩容,有可能无效扩容(插入后如果扩容,如果没有再次插入,就会产生无效扩容)。

ConcurrentHashMap:

底层采用分段的数组+链表实现,线程安全。

通过把整个Map分为N个Segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry的value变量是 volatile的,也能保证读取到最新的值。)。

Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术。

1000个哈希桶存50个元素不重复的概率

3、理解什么时hash容器以及hash容器的特点

Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射,

pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不

同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

C++使用Hash的容器是hash_map,hash_map目前并没有纳入C++ 标准模板库中,但几乎每个版本的STL都提供了相应的实现。

hash_map基于hash

table(哈希表)。哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当

前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。

其基本原理是:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值

(即数组下标,hash值)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应

“类”所对应的地方,称为桶。

但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。 总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。

hash_map,首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。其插入过程是:

1. 得到key

2. 通过hash函数得到hash值

3. 得到桶号(一般都为hash值对桶数求模)

4. 存放key和value在桶内。

其取值过程是:

1. 得到key

2. 通过hash函数得到hash值

3. 得到桶号(一般都为hash值对桶数求模)

4. 比较桶的内部元素是否与key相等,若都不相等,则没有找到。

5. 取出相等的记录的value。

hash_map中直接地址用hash函数生成,解决冲突,用比较函数解决。这里可以看出,如果每个桶内部只有一个元素,那么查找的时候只有一次比较。当许多桶内没有值时,许多查询就会更快了(指查不到的时候).

4、文件f建立简单的hash桶,使用100个hash桶,桶目录需要多少个磁盘块

题目描述:设文件F具有10000个记录,每个记录50字节,其中10字节用来表示文件的键值。每个磁盘块大小1000字节,指向磁盘块的指针占5字节,不允许记录跨两个块。

(1)如果为文件F建立简单的Hash索引,使用100个Hash桶,则桶目录需要多少磁盘块?平均每个桶需要多少磁盘块?

(2)如果为文件F建立B+索引,各磁盘块尽量填满,需要多少磁盘块存储索引?

答案:

(1)桶目录是是一个列表,100个桶可以存放在尺寸为100的int型数组中,一个int型占4个字节的话,总共400个字节,而一个磁盘块1000个字节,所以桶目录存放于1个磁盘块中;

给了100个Hash桶,一个桶里放100个记录,100个记录总共100*50=5000个字节,所以需要5000/1000=5个磁盘块。

(2)建立B+索引,从叶子节点算起,求出每个叶子节点的在尽量放满一块磁盘的情况下共存了多少条记录:10×R+5×R<=1000,R取66,所以叶节点的总数为?10000/66?=152个,即叶节点需要152个磁盘块;因为刚才计算出R=66,即上层节点是66叉树,那么上层节点数有?152/66?=3个,则需要3个磁盘块;再往上层节点走,只需要安排1个节点,即到达根节点。所以总共需要152+3+1个磁盘块。

上一篇:没有了
技术干货
零基础学习
行业多年深耕,从这报名,学费立减800
  • 岳同学180****1241刚刚成功领取
  • 胡同学134****6431刚刚成功领取
  • 李同学150****6122刚刚成功领取
  • 张同学136****2231刚刚成功领取
  • 孙同学178****5521刚刚成功领取
  • 齐同学156****7788刚刚成功领取
猜你喜欢
查看更多
相关推荐
查看更多
现在学习,我的薪资能达到多少?
立即报名

联系我们:

Q:2638333071

鄂ICP备2023015464号