古云网站建设,一般网站建设需要哪些东西,微平台小程序,中国十大公关公司1.哈希表定义 哈希表#xff08;hash table#xff0c;也叫散列表#xff09;#xff0c;是根据关键码值#xff08;key value#xff09;而直接进行访问的数据结构。也就是说#xff0c;它通过把关键码值映射到表中一个位置来访问记录#xff0c;以加快查找的速度。这…1.哈希表定义 哈希表hash table也叫散列表是根据关键码值key value而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。这个映射函数叫散列函数存放记录的数组叫散列表。 哈希表可以提供快速的插入和查找工作哈希表运算的非常快而且编程实现也比较容易。哈希表是数组和链表结构。 2.哈希表的原理 1.哈希表是链表和数组实现的(数组里面存储的元素是链表的头结点) 2.哈希表是环形数组实现的 什么是环形数组呢?
就是近似于环,数组的最大索引后面就是0索引,这种思想主要是通过取模计算实现的,
主要公式: index index % arr.length
就按照上图举例吧: 例如 计算出hash值为 10 10 % 8 2 所以应该存放 2 索引的位置 3.为什么Jdk会在链表长度超过8时转换为红黑树
正常数据情况下,就算数据量比较大,也不会出现超过8的情况
但是为什么会用这种机制呢
这种机制呢,主要是为了防范于未然,防止被攻击,有些人专门造一些攻击的Hash数据(这些hash值都会相互之间冲突),就会形成一个非常长的链表,会使你整个服务器下降,
主要目的:为了防止被恶意攻击 4.为什么Jdk的底层数组长度都是2^n
.位运算符()比模运算(%)效率高这样做可以提高效率。 它对应的二进制表示中只有一位是1其余位都是0。在这种情况下计算哈希值h与哈希表长度m的取模运算等价于对2^n取模可以使用位运算实现即 h (m - 1)。
所以长度为2 ^ n就会有一个规律: [hash (数组长度-1)] 等价于 [hash % 数组长度]
这样的做法的好处是当哈希表长度是2^n时可以用位运算来代替较慢的取模运算从而提高哈希表的性能。并且由于2^n的二进制表示中只有一位是1因此在使用位运算计算哈希表索引时可以保证结果均匀分布减少哈希碰撞的概率。
需要注意的是即使哈希表的长度不是2^n仍然可以使用位运算来代替取模运算。但是这样做会使得位运算的效率降低并且不能保证哈希值均匀分布容易导致哈希冲突影响哈希表的性能。 3.代码原理分析
3.1添加
1.hash表在添加的使用key.hashCode()计算出的键的hash值
2.再利用位运算符数组长度 - 1(% 数组长度)计算出应该要存的下标
3.接下俩就是数组中有元素吗? 3.1 没有则直接存 3.2 有的话,一直往后找找到最后一个元素添加在它的尾部
3.2删除
删除的原理:主要思想就是找到删除元素上一个节点(如果是头部,则头部下一个节点为空)
1.根据要删除的元素计算其hash值并找到对应的数组索引。
2.在该索引位置查找元素如果存在则执行删除操作。
3.删除元素后根据具体情况可能需要进行以下操作 3.1 如果删除后该位置没有其他元素则直接将该位置设为null表示该位置为空。 3.2如果删除后该位置有其他元素可能是发生了哈希冲突则可能需要进行链表或其他数据结构的调整以保持哈希表的正确性。
具体删除时的操作流程可能因不同的哈希表实现而有所不同。例如对于开放寻址法的哈希表实现在删除元素时可能会使用查找下一个空槽的方式来处理哈希冲突。而对于拉链法的哈希表实现在删除元素时可能需要遍历链表结构并进行节点的删除操作。
需要注意的是哈希表的删除操作可能会导致哈希表的负载因子过低或链表过长等问题影响哈希表的性能。为了保持哈希表的高效性可能需要根据具体情况进行动态缩容、重新哈希或其他优化操作。
3.3扩容
哈希表的扩容是为了保持哈希表的负载因子在一个可接受的范围内从而保持哈希表的性能稳定。
当哈希表中的元素数量达到一定阈值(0.75)时就会触发扩容操作。具体的扩容原理如下
1.创建一个新的更大的数组通常将数组长度扩大为原来的两倍。
2.遍历原来的哈希表将每个元素重新计算哈希值并放入新的数组中的对应位置
3.这个过程被称为重新哈希Rehashing它会根据新数组大小重新计算元素的存储位置以确保元素在新数组中的分布更为均匀减少哈希冲突。
4.将新的数组设置为哈希表的底层数组用于存储元素。
4.代码实现
注意:这里我怕不好理解我没有用位运算符()全部用了%
4.1准备工作
定义节点类,和定义成员变量
// 哈希表的代码实现
public class HashTableK,V{// 定义哈希表节点class HashNodeK, V{private final K key;//键private V value;//值private HashNodeK, V next;//下一个节点的引用public HashNode(K key, V value) {this.key key;this.value value;this.next null;}public K getKey() {return key;}public V getValue() {return value;}public void setValue(V value) {this.value value;}public HashNodeK, V getNext() {return next;}public void setNext(HashNodeK, V next) {this.next next;}}private int SIZE;//定义数组的长度private final double LOAD_FACTOR 0.75; // 负载因子用于决定何时进行扩容private int size; // 哈希表中节点的数量private HashNodeK,V[] table;//定义一个存链表的数组public HashTable(int initialCapacity) {//初始化数组this.SIZE initialCapacity;table new HashNode[SIZE];this.size 0;//初始化节点数量为0}}
4.2计算键的应该存入的下标 private int getHash(K key) {//利用jdk的哈希算法来产生一个随机数return Math.abs(key.hashCode() % SIZE);//获得键的hash值应放入的索引,取绝对值以保证正数}4.3扩容
//扩容private void resize() {int newSize SIZE * 2; // 新的哈希表大小为原来的两倍HashNodeK, V[] newTable new HashNode[newSize]; // 创建新的数组for (int i 0; i SIZE; i) {HashNodeK, V current table[i]; // 获取原数组的每个链表的头节点while (current ! null) {K key current.getKey();V value current.getValue();// 根据新的数组大小重新计算哈希值int hash Math.abs(key.hashCode() % newSize);// 插入节点到新的数组中if (newTable[hash] null) {//头结点newTable[hash] new HashNode(key, value);} else {//非头结点HashNodeK, V newNode newTable[hash];while (newNode.getNext() ! null) {//找到next不为null的节点进行存储newNode newNode.getNext();}newNode.setNext(new HashNode(key, value));}current current.getNext(); // 继续遍历原数组的下一个节点}}table newTable; // 将引用指向新的数组SIZE newSize; // 更新数组大小}
4.4添加
public void put(K key,V value){//向hash表中插入键值对int hash getHash(key);//计算键的hash值放入的索引if (table[hash] null){ //为空table[hash] new HashNode(key,value);//直接插入节点}else {//不为空HashNodeK, V current table[hash];while (current.getNext() ! null) { // 遍历链表直到找到最后一个节点if (current.getKey().equals(key)) { // 如果找到键相同的节点current.setValue(value); // 更新值return;}current current.next;}//找不到就判断最后一个是不是if (current.getKey().equals(key)) { // 如果最后一个节点的键与目标键相同current.setValue(value); // 更新值} else { // 如果最后一个节点的键与目标键不同current.setNext(new HashNode(key, value)); // 插入新节点作为最后一个节点的下一个节点}}// 检查负载因子是否超过阈值如果超过则进行扩容if ((double) size / SIZE LOAD_FACTOR) {resize();}}
4.5删除
public void remove(K key) { // 移除指定键的节点int hash getHash(key); // 计算键的哈希值HashNodeK, V previous null; // 记录前一个节点HashNodeK, V current table[hash]; // 获取对应索引位置的节点while (current ! null) { // 遍历链表if (current.getKey().equals(key)) { // 如果找到键相同的节点if (previous null) { // 如果当前节点为链表的第一个节点table[hash] current.getNext(); // 将下一个节点设为新的头节点} else { // 如果当前节点不是链表的第一个节点previous.setNext(current.getNext()); // 将上一个节点的next指向当前节点的下一个节点跳过当前节点}return;}previous current; // 更新前一个节点current current.getNext(); // 继续遍历下一个节点}}
4.5判空
public boolean isEmpty() { // 判断哈希表是否为空for (int i 0; i SIZE; i) { // 遍历数组if (table[i] ! null) { // 如果存在非空的节点return false; // 表示哈希表不为空}}return true; // 如果数组中所有元素都为空则返回true表示哈希表为空}
4.6获得键对应的值 public V get(K key) { // 根据键获取值int hash getHash(key);HashNodeK,V current table[hash];//获取对应索引的位置while (current ! null) { // 遍历链表if (current.getKey().equals(key)) { // 如果找到键相同的节点return current.getValue(); // 返回对应的值}current current.getNext(); // 继续遍历下一个节点}return null; // 如果未找到对应的键则返回null}
4.7获得节点的个数 public int size() { // 获取哈希表中节点的数量int count 0; // 计数器for (int i 0; i SIZE; i) { // 遍历数组HashNodeK, V current table[i]; // 获取对应索引位置的节点while (current ! null) { // 遍历链表count; // 计数器加一current current.getNext(); // 继续遍历下一个节点}}return count; // 返回计数器的值即哈希表中节点的数量}
