阿里面试90%以上会问到的数据结构;HashMap
BAT面试必问;
关于hashmap,你知道多少?你知道hashmap的工作原理吗?
1.该问题很有深度
2.能答出多少决定岗位和薪资.
3.问题的方式多种多样
一.首先我们了解下HashMap是什么
HashMap是Java常用的用来储存键值对的数据结构,它是线程不安全的,可以储存null键值,这些大家经常用,也都知道,接下来根据源码分析一下HashMap的实现。
1、实现原理
HashMap采用数组散列+链表的方式来储存键值对,键值对的对象实现如下:
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; …… }
通过一个Entry的数组table就实现了多个对象的保存,使用哈希值和键值解决了在插入和查找时的冲突。
2、put方法,写入键值对
public V put(K key, V value){ //如果 key 为 null,调用 putForNullKey 方法写入null键的值 if (key == null){ return putForNullKey(value); } //根据 key 的 keyCode 计算 Hash 值 int hash = hash(key.hashCode()); //查找hash值在table中的索引 int i = indexFor(hash, table.length); // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历链表查找是否在链表中有相同key的Entry for (Entry<K,V> e = tablei; e != null; e = e.next) { Object k; //找到与插入的值的key和hash相同的Entry if (e.hash == hash && ((k = e.key) == key|| key.equals(k)){ //key值相同时直接替换value值,跳出函数 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如果 i 索引处的 Entry 为 null 或者key的hash值相同而key不同 ,则需要新增Entry modCount++; // 将 key、value 添加到 i 索引处 addEntry(hash, key, value, i); return null; }
在put方法中解决hash碰撞的方式很清楚,即当两个entry的hash值相同时,需要对key值是否相同进行判断,只有key和hash都相同,才能进行修改,否则认为不是同一个entry。
3.addEntry的实现
代码:
void addEntry(int hash, K key, V value, int bucketIndex) { // 获取指定 bucketIndex 索引处的 Entry Entry<K,V> e = tablebucketIndex; tablebucketIndex = new Entry<K,V>(hash, key, value, e); // 如果 Map 中的 key-value 对的数量超过了极限 if (size++ >= threshold) resize(2 table.length); }
在创建新Entry时如果table的bucketIndex处有元素的话,创建时需要将entry的next设置为原先存储的元素。
二,HashMap工作原理
以下为目录,有需要完整进阶视频可以加Android进阶群;701740775免费获取
1.目录
2.顺序表与链表
3.Hsh表
4.Hash源码
5.碰撞
需要完整进阶视频详解可以加Android进阶群;701740775免费获取!
附录Android高级技术大纲和进阶视频;
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
爱奇艺技术分享:爱奇艺Android客户端启动速度优化实践总结
本文由爱奇艺技术团队原创分享,原题《爱奇艺Android客户端启动优化与分析》。 1、引言 互联网领域里有个八秒定律,如果网页打开时间超过8秒,便会有超过70%的用户放弃等待,对Android APP而言,要求更加严格,如果系统无响应时间超过5秒,便会出现ANR,APP可能会被强制关闭,因此,启动时间作为一个重要的性能指标,关系着用户的第一体验。 爱奇艺安卓APP非常重视启动速度的优化,本文将从启动过程、启动时间测量、启动优化、以及后续监控等方面分享我们在启动优化方面积累的经验。 相关文章: 《移动端IM实践:Android版微信如何大幅提升交互性能(一)》 《移动端IM实践:Android版微信如何大幅提升交互性能(二)》 《移动端IM实践:iOS版微信界面卡顿监测方案》 《微信团队原创分享:Android内存泄漏监控和优化技巧总结》 《美图App的移动端DNS优化实践:HTTPS请求耗时减小近半》 (本文同步发布于:http://www.52im.net/thread-2221-1-1.html) 2、启动模式 要准确的测量APP的启动时间,首先我们要了解APP整个启动过程。 启动...
- 下一篇
短视频app开发过程中的“灵魂”所在
对于短视频app开发业务来讲,完整的流程应该同时具备视频的本地编辑、云处理和用户预览。抖音作为短视频市场中的“成功案例”,许多软件开发公司纷纷以抖音为例,顺应短视频市场的发展趋势,纷纷开始向抖音类的短视频应用靠拢。那么开发短视频的过程中,都有哪些主要的业务部分呢,今天就来跟大家简单分享一下。视频采集移动端的设备可以根据用户所需的分辨率进行相应的视频采集,并且以文件的形式进行保存。关于视频采集部分,在Android和ios平台都可以依靠相对应的平台接口,进行对应的分辨率进行数据采集。 视频处理这一部分主要是用来处理视频的滤镜、水印、剪辑等效果,通常使用FFmpeg,对视频进行相应的效果处理,其中也可以使用某些系统自带的优化接口,或者也可以使用图像处理的相应算法来进行视频的效果实现。视频上传视频上传主要是指与视频服务平台进行交互,主要问题就是需要保证视频上传的速度,一般来说,这些服务平台都会根据用户的位置来分配最近的服务节点,从而保证视频的上传速度。说实在的,如果短视频的上传速度太慢,我相信不会有人会把这款app在手机上留存太久。服务平台即提供视频的云处理服务,这里指的处理服务主要是提供视...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8编译安装MySQL8.0.19
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Red5直播服务器,属于Java语言的直播服务器
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- Hadoop3单机部署,实现最简伪集群
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题