HashMap和HashSet |
您所在的位置：网站首页 › 遍历arraylist集合获取每个学生的成绩 › HashMap和HashSet |
HashMap和HashSet
|
Map和Set是专门用来进行搜索的接口，不能直接实例化对象，可以通过HashMap实例化对象，效率与其具体的实例化子类有关。相对直接遍历或二分查找来说，Map和Set更适合动态查找，如添加，删除，和定位通讯录的内容，使用HashMap可以有很快的访问速度O（1）。HashMap是Java程序员使用频率最高的用于动态查找的数据类型，它存储的是键值对（key-value)映射。相同的是，HashMap和HashSet都是无序的，不会记录添加的顺序，允许有null值（HashMap只允许有一条键值为null），并且线程不安全。不同的是，HashMap继承于AbstractMap，实现了Map，Cloneable，Serializable接口，根据key的HashCode值存储数据。HashSet实现了Set接口, 内部只存储了Key，是不允许有重复元素的集合。 哈希表
哈希冲突 在哈希表中，如果有两个元素的哈希地址相同，称为哈希冲突。常见的解决哈希冲突的方法有：闭散列和开散列。 1. 闭散列 又称“开放定址法”，当发生哈希冲突时，哈希表未被装满，可以把key存放到冲突位置的下一个空位中，有以下两种方法可以寻找到“下一个”位置。 1.1 线性探测 最简单的方法叫做线性探测。发生冲突时，在散列索引之后的索引序列中寻找另一个位置。 //哈希函数： Hash（key)=key%capacity(数据的长度） hash(obj) + 1 + 2 + 3 + ...1.2 二次探测 线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，其中在冲突时探索以下备选位置序列： //二次探测 Hi = (H0 + i^2)% m, 或者： Hi = (H0 - i^2)% m。 其中：i = 1,2,3…，是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置， m是表的大小。 hash(obj) + 1 + 4 = 22 + 9 = 32 + 16 = 42 + ...在合理的情况下，我们是否真的能够用这种方法找到一个开放的插槽。一个相对简单的数论结果可以保证，如果容量为素数且负载不超过0.5，则探测序列可以保证成功。闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。 2. 开散列 又称“链地址法(开链法)”，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。开散列可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。 如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如： 1. 每个桶的背后是另一个哈希表 2. 每个桶的背后是一棵搜索树 3.进行扩容，降低负载因子，降低冲突 实现： private static class Node{ private int key; private int value; Node next; public Node(int key, int value){ this.key=key; this.value=value; } private Node[] array; private int size; private static final double LOAD_FACTOR=0.75; public int put(int key,int value){ int index=key% array.length; //在链表中查找key所在的节点 for(Node cur=array[index];cur!=null;cur=cur.next){ if(key==cur.key){//找到key所在的节点，更新 int oldValue=value; cur.value=value; return oldValue; } } //所有节点都不是key，插入一个新的节点 Node node=new Node(key,value); node.next=array[index]; array[index]=node; size++; if(loadFactor()>=LOAD_FACTOR){ resize(); } return -1; } private void resize(){//扩容 Node[] newArray=new Node[array.length*2]; for(int i=0;i |
【本文地址】
今日新闻 |
推荐新闻 |