Java集合系列之HashMap源码分析-创新互联
前面我们已经分析了ArrayList和LinkedList这两个集合,我们知道ArrayList是基于数组实现的,LinkedList是基于链表实现的。它们各自有自己的优劣势,例如ArrayList在定位查找元素时会优于LinkedList,而LinkedList在添加删除元素时会优于ArrayList。而本篇介绍的HashMap综合了二者的优势,它的底层是基于哈希表实现的,如果不考虑哈希冲突的话,HashMap在增删改查操作上的时间复杂度都能够达到惊人的O(1)。我们先看看它所基于的哈希表的结构。
创新互联主要从事做网站、成都做网站、网页设计、企业做网站、公司建网站等业务。立足成都服务扎兰屯,10多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108从上图中可以看到,哈希表是由数组和链表共同构成的一种结构,当然上图是一个不好的示例,一个好的哈希函数应该要尽量平均元素在数组中的分布,减少哈希冲突从而减小链表的长度。链表的长度越长,意味着在查找时需要遍历的结点越多,哈希表的性能也就越差。接下来我们来看下HashMap的部分成员变量。
//默认初始容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //默认加载因子, 指哈希表可以达到多满的尺度 static final float DEFAULT_LOAD_FACTOR = 0.75f; //空的哈希表 static final Entry<?,?>[] EMPTY_TABLE = {}; //实际使用的哈希表 transient Entry[] table = (Entry []) EMPTY_TABLE; //HashMap大小, 即HashMap存储的键值对数量 transient int size; //键值对的阈值, 用于判断是否需要扩增哈希表容量 int threshold; //加载因子 final float loadFactor; //修改次数, 用于fail-fast机制 transient int modCount; //使用替代哈希的默认阀值 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; //随机的哈希种子, 有助于减少哈希碰撞的次数 transient int hashSeed = 0;
新闻标题:Java集合系列之HashMap源码分析-创新互联
链接分享:http://pwwzsj.com/article/pdehi.html