专注培养泛IT高端人才

陕西新榜样官方网站

您的位置: 主页 > 新闻动态 > IT资讯 >

数据处理与减少繁余

来源:陕西新榜样软件科技有限公司 发布时间:2018-07-13 浏览量:

  在工作中没有什么问题是不能被解决的,一个大问题可以被分解为无数个小问题,然后解决掉它。

  就数据处理,降低数组大小而言,《数据结构与算法分析.Java语言描述》一书有明确的解释,采取开放寻址法,简单方便。

  当然,不是所有人都这么用,JDK的HashMap使用的则是分离链接法(separate chaining)。不同:增加了桶的概念来保存冲突的数据;进行求余运算来降低数组大小。

  那么,就谈谈Java中的HashMap吧。HashMap的本质依然是数组,而且是一个不定长的多维数组。

  HashMap中的数组保存链表的头节点。

  一、保存数据

  计算key的hashCode,再与数组长度进行求余运算得到数组下标(链表头节点)。

  如果该位置为空,生成一个新的链表节点并保存到该数组。

  如果该位置非空,循环比对链表的每一个节点:已经存在key相同的节点,覆盖旧节点;不存在key相同的节点,将新节点作为链表的尾节点(注:查看JDK1.8中的源码,新节点总是加入到链表末尾,而不是如JDK1.6一般作为链表头节点)。

  二、查找数据

  计算key的hashCode,再与数组长度进行求余运算得到数组下标(链表头节点)。如果链表不为空,先比对首节点,如果首节点key相同(hashCode相同且equals为true),直接返回首节点的value;首节点key不同则顺序遍历比对链表其它节点,返回key相同的节点的value(未找到key相同的节点则返回null)。

  HashMap引入链表的目的就是为了解决上一节讨论过的重复冲突问题。

  三、注意事项

  如果所有key的hashcode相同,假定均为0,则0%4 = 0,所有元素就会都保存到链表0,保存和查找每一个数据都需要遍历链表0。那么,此时的HashMap实质上已经退化成了链表,时间复杂度也从设计的O(1)上升到了O(n/2)。

  为了尽可能地让HashMap的查找和保存的时间复杂度保持在O(1),就需要让元素均匀地分布在每一个链表,也就是每一个链表只保存一个元素。

IT培训 服务