哈希表基础知识

Hash表的基础知识

关于Hash表

哈希表(Hash Table)是根据关键码(key) 值(value)进行直接访问的数据结构。哈希表最大的优点是高效,在哈希表中插入、删除或查找一个元素都只需要O(1)的时间。因此,哈希表常用来优化时间效率。

哈希表的对应类型

在Java中,哈希表有两个对应的类型,即HashSet 和 HashMap。

关于HashSet

HashSet这个类实现了Set集合。这个类允许null。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

并且HashSet提供了三个构造函数:

  • 1、第一个是无参构造函数,此函数会创建一个大小为16的容器,加载因子是0.75

public HashSet()
Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75).

Set的子类大部分是无序的、不可重复(TreeSet是有序的)。

  • HashSet:线程不安全,存取速度快,内部实现是HashMap的key entry
    1、默认初识容量为16(为什么是16,16是2^4,可以提高查询效率,另外,32=16<<1,扩容只需左移,速度很快)。
    2、加载因子为0.75:即为 元素个数 超过 容量长度的0.75倍时,进行扩容
    3、扩容增量:增加一倍,HashSet的容量为16,一次扩容后时容量为32

那么接下来思考,容器怎么保证添加的元素不重复的呢?(由于Set取值的时候调用值本身来取值的,所以不能重复,如果重复了,根据值取的时候就不知道取哪一个。List是根据下标map是根据具体key取值)

接下来看一下HashSet的add方法:
哈希表基础知识
这个方法实际上是添加的一个put方法,描述的意思是:向这个set集合中添加元素,如果这个元素没有在集合中则添加到这个集合中。如果这个集合已经存在元素调用将离开。
e是add添加的元素,而PRESENT 在HashSet中是这样定义的 private static final Object PRESENT = new Object();

  • 2、public HashSet(Collection<? extends E> c)
    构造一个包含指定集合中的元素的新集合
  • 3、public HashSet(int initialCapacity)
    构造一个新的空集合; 背景HashMap实例具有指定的初始容量和默认负载因子(0.75)。
  • 4、HashSet(int initialCapacity, float loadFactor)
    构造一个新的空集合; 背景HashMap实例具有指定的初始容量和指定的负载因子。

HashSet的常用函数

HashMap

上一篇:java 十进制互转十六进制、二进制


下一篇:react文档阅读收获