拉链法用途
解决hash冲突（即put操作时计算key值问题）。
拉链法原理
把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。
有m个散列地址就有m个链表，同时用指针数组A[0,1,2…m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以A[i]为指针的单链表中。A中各分量的初值为空指针。
拉链法原理解释
HashMap是一个数组，数组中的每个元素是链表。put元素进去的时候，会通过计算key的hash值来获取到一个index，根据index找到数组中的位置，进行元素插入。当新来的元素映射到冲突的数组位置时，就会插入到链表的头部。
HashMap采用拉链法将HashMap的key是转化成了hashcode，但hashcode可能重复，所以采用求交集方式解决冲突。
举例如下
有序集合a1={1,3,5,7,8,9}，有序集合a2={2,3,4,5,6,7}
两个指针指向首元素，比较元素的大小：
（1）如果相同，放入结果集，随意移动一个指针
（2）否则，移动值较小的一个指针，直到队尾
好处：
（1）集合中的元素最多被比较一次，时间复杂度为O(n)。
（2）多个有序集合可以同时进行，这适用于多个分词的item求url_id交集。
这个方法就像一条拉链的两边齿轮，然后逐个对比，故称为拉链法。
扫一扫
2960
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
