hashmap原始碼面試分析

itread01 2020-11-06 01:23:33
hashmap 原始 分析


####HashMap原始碼問題解析 1. **問: 說一說對hash的理解** 答: hash是對任意長度的輸入輸出為相同長度的輸出 2. 問: hash演算法的問題 答: hash衝突問題 3. 問: hash衝突是否可以避免 答: 不可以避免,只能儘量規避 4. **問: 優秀的hash演算法有什麼特性** 答: 1. 任何微小的變化hash的結果都不相同 2. hash不可逆 3. 長字串的hash效率要高 4. hash值儘量雜湊平均 5. 相同的值hash值相同 5. **問: hashmap的資料結構** 答: 以1.8為例 陣列+連結串列+紅黑樹 資料儲存在node物件中,node中有key value next hash等欄位 6. 問: 散列表的初始長度是多長 答: 預設是16 7. 問: 散列表是什麼時候建立 答: 第一次put的時候建立(懶載入) 8. 問: 預設的負載因子是多少,負載因子的作用 答: 空參構造建立的hashmap的負載因子是0.75,作用是當node數量大於陣列長度的0.75的時候進行resize擴容 9. **問: 連結串列轉化紅黑樹需要什麼條件** 答: 需要兩個條件 連結串列長度大於等於7並且陣列的長度大於等於64才進行樹化 10. **問node物件的hash值是怎麼得來的,為什麼這麼操作** 答: 是根據key的hashcode值在與key的hashcode的高16位異或操作得來的,是為了在陣列中分佈的更加隨機均勻,因為hashmap的資料計算陣列下標的方法是(tab.length-1)&hash,tab.length大部分情況下小於2^16也就是25536(規則表明tab.length必須是2的次方數) 所以大部分情況下是hash的低16位參與運算,為了讓hash更加隨機均勻,多一次與key的hashcode異或運算來加強hash值的隨機分佈,讓hashcode沒一位都參與到運算中 11. 問: **hashmap put方法的詳細流程** 答: key經過定址查到在陣列中的下標 1. 如果陣列下標為null直接存入node 2. 如果不為空比較值 相同覆蓋 如果是樹則按紅黑樹規則放入 如果不是樹 進行尾插連結串列長度大於等於7並且陣列長度大於64轉樹 長度超過閾值resize 12. 問: 紅黑樹的原則 答: 1. 葉子節點到根節點的路徑黑色節點數量一致(黑高) 2. 葉子節點都是黑色的 3. 不能有兩個紅色的節點相連 4. 根節點一定是黑色的 5. 插入的節點一定是紅色的(紅插) 13. 問: jdk1.8hashmap為什麼引入紅黑樹 答: 因為連結串列太長的話會導致查詢效率降低hash的目的是儘量實現o(1)的,連結定址很慢 14. 問: hashmap什麼時候會觸發擴容 答: put操作的時候,有個欄位記錄資料量當大於擴容閾值的時候擴容 15. 問: hashmap怎麼擴容 答: 陣列長度一定是2的次方數,每次擴容是原先長度左移一位<<1 16. **問: 老陣列的資料怎麼遷移到新陣列中** 答: 1. hash未衝突的直接根據新的陣列長度計算放入即可 2. 如果已經成紅黑樹 3. 已經是連結串列未成樹會hash&舊陣列長度(oldcap) 等於0的放低鏈 不等於的放高鏈 低鏈的放原來的index 高鏈放原來的index+oldlength的位置 解釋:在hashmap定址演算法計算得出(hash&(length-1)) 一條連結串列的資料肯定會分成兩個連結串列 位置一個是原index 另一個是原index+oldlength 原先的length長度為16 二進位制為10000 那麼length就是16-1 =15(1111)就是hash&1111 以第15個桶為例,那麼hash的值就可能是01111或者11111 擴容後length變為32 二進位制為100000 hash&11111 那麼如果15這個桶位置原先hash是01111的node就放在他原先的15的這個位置,hash為11111的就放在 32這個桶的位置 01111 & 10000 = 0 這個放15這個位置 11111 & 10000 != 0 放32 15+16 = 31這個位
版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
https://www.itread01.com/content/1604511062.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云