chapter_hashing/summary/

[giscus[bot]]

chapter_hashing/summary/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_hashing/summary/

[iron-irax]

小结不见了。

[krahets]

🫡收到，我会尽快补上

[OMG1-1]

小结不见了

[krahets]

对不起 🧎 ，一直在写新的章节

[wxdl99]

在学习哈希冲突一节的时候，有个疑问就是使用多次哈希的时候会不会也有需要标记被删除元素的问题；到小结的时候还是存在这个疑问，直到看到Q&A里面（开放寻址法“都“有不能直接删除元素的缺陷）才解决这个疑问。建议在正文的部分强调一下，或者把这个问题写在开放寻址下面，而不是写在线性寻址下面。

[krahets]

谢谢建议 已加～

[showlibia]

DAY5

[Shenxiaodong30]

打卡

[advwei]

由于兴趣出发，python也是自己摸索的学习，一直没有系统的概念。所以看见哈希表第一节时就有这是不是就是python中的字典的疑惑？
看完这章后我总结的是这样【字典类似于哈希表，因为字典的实现是基于哈希表，两者都是一种键值对的数据结构，将建映射到值是通过哈希算法实现的，哈希算法可以实现将大空间映射到小空间且时间效率都是O(1)，而映射过程中出现的将不同输入映射到同一个输出的情况叫做哈希冲突】
不知道这样理解有没有问题，非常感谢K神及项目人员的付出，此书犹如明灯一样极大的给予了一个非科班社畜学习的莫大帮助。

[krahets]

谢谢鼓励！Python 中的字典 dict 实际上就是哈希表 hash table ，只是 python 给它起了一个更加生活化的名字。

[advwei]

好滴，谢谢！！！

[shizi327]

要是可以加几道大厂的笔试题就无敌了

[krahets]

想刷题的话可以看看这里～ https://github.com/krahets/LeetCode-Book

[Kore-yoshi]

无敌

[spikenevergiveup]

打卡

[Q1ufeng]

打卡，感谢作者捏

[1395797365]

为什么哈希算法不提倡用异或
异或后稳定性不是非常高吗

[1395797365]

小白

[Hydrocarbon2023]

异或满足交换律，不利于处理顺序颠倒的情况

[NingZiXi]

哈希函数的最后一步通常涉及对数组长度 n 取模（取余），其目的是将哈希值映射到一个有效的数组索引范围内。这个数组索引范围通常就是哈希表的桶数量，也就是哈希表内部存储数据的位置。

具体来说，当哈希函数计算出一个哈希值后，该哈希值可能会非常大，远远超出哈希表数组的实际大小。为了将这个大的哈希值映射到数组的索引范围内，可以使用取模运算。

取模运算（取余运算）是对一个数除以另一个数，得到的余数就是取模的结果。在哈希表中，通常会将哈希值对数组的长度 n 进行取模，以确保得到的索引值在数组范围内。

例如，如果哈希值为 h ，数组长度为 n ，那么对数组长度 n 取模的结果就是 h mod n 。这个结果将落在 0 到 n-1 之间，即有效的数组索引范围内，然后可以使用这个结果来确定存储位置。

这样做的目的是保证哈希值被分布到哈希表中的桶中，以便能够快速地访问和管理存储在哈希表中的数据。

[joesima]

Thanks a lot, 😊

…

On Thu, Feb 22, 2024, 5:33 PM 宁子希 ***@***.***> wrote: 哈希函数的最后一步通常涉及对数组长度 n 取模（取余），其目的是将哈希值映射到一个有效的数组索引范围内。这个数组索引范围通常就是哈希表的桶数量，也就是哈希表内部存储数据的位置。 具体来说，当哈希函数计算出一个哈希值后，该哈希值可能会非常大，远远超出哈希表数组的实际大小。为了将这个大的哈希值映射到数组的索引范围内，可以使用取模运算。 取模运算（取余运算）是对一个数除以另一个数，得到的余数就是取模的结果。在哈希表中，通常会将哈希值对数组的长度 n 进行取模，以确保得到的索引值在数组范围内。 例如，如果哈希值为 h ，数组长度为 n ，那么对数组长度 n 取模的结果就是 h mod n 。这个结果将落在 0 到 n-1 之间，即有效的数组索引范围内，然后可以使用这个结果来确定存储位置。 这样做的目的是保证哈希值被分布到哈希表中的桶中，以便能够快速地访问和管理存储在哈希表中的数据。 — Reply to this email directly, view it on GitHub <#100 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ASCIKGKXXJJGWPXTTCZFO6TYU4GFFAVCNFSM6AAAAAAS4X33BKVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4DKNJUGM2TO> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[HuaWang135608]

Over

[williamherry]

对key进行哈希运算找到桶的索引，桶内不止保存了value，key也保存了，得到桶的索引要进一步比对key是吗？

[krahets]

是的

[sevenzard]

K大，对于这句话“如果一个功能能够在相同的时间复杂度下使用数组或链表实现，那么通常比哈希表更快。这是因为哈希函数计算需要开销，时间复杂度的常数项更大“，可以举个具体的例子吗

[krahets]

假设我们的 key 是整数 1 ～ 100 ，那么可以用哈希表，也可以用一个长度为 100 的数组来存，后者就比前者更简单更快

[daiDai-study]

打卡

[Dannytaotao]

2024.5.16 finish

[DayDayYES]

找到寻找大质数的意义了，哈希算法通常采用大质数作为模数，以最大化地保证哈希值均匀分布，减少哈希冲突。

[Bluesmmm]

第六章打卡~

[921000]

public class HashTable {

private int size;

private int capacity;

private Node[] nodes;


class Node {
    public int key;

    public int value;

    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }

    public Node() {
    }

}


public HashTable(int capacity) {
    this.capacity = capacity;
    nodes = new Node[capacity];
}


/**
 * 负载因子 0.75 判断是否超过0.75
 */
public boolean isOverLoad() {
    return size > capacity * 0.75;
}


public void put(int key, int value) {
    // 判断是否需要扩容
    if (isOverLoad()) {
        resize();
    }
    putVal(key, value, nodes);
}

public int get(int key) {
    int index = hash(key);
    if (nodes[index] == null) {
        return -1;
    }
    Node node = nodes[index];
    while (node.next != null) {
        if (node.key == key) {
            return node.value;
        }
        node = node.next;
    }

    return node.key;
}


public void remove(int key) {
    int index = hash(key);
    if (nodes[index] == null) {
        return;
    }
    Node node = nodes[index];
    if (node.key == key) {
        nodes[index] = node.next;
        size--;
        return;
    }

    while (node.next != null) {
        if (node.next.key == key) {
            node.next = node.next.next;
        }
        node = node.next;
    }
    size--;
}

private void putVal(int key, int value, Node[] nodes) {
    int index = hash(key);
    if (nodes[index] == null) {
        nodes[index] = new Node(key, value);
        size++;
        return;
    }
    Node node = nodes[index];
    while (node.next != null) {
        node = node.next;
    }
    node.next = new Node(key, value);
    // 这里可以将链表转成红黑数
    size++;
}

private void resize() {
    capacity = capacity * 2;
    Node[] newNodes = new Node[capacity];
    size = 0;
    for (Node value : nodes) {
        if (value == null) {
            continue;
        }
        Node node = value;
        putVal(node.key, node.value, newNodes);
        while (node.next != null) {
            putVal(node.next.key, node.next.value, newNodes);
            node = node.next;
        }
    }
    nodes = newNodes;
}

public int hash(int key) {
    // 这里可以使用各种hash算法 demo 使用简单的取模
    return key * 13 % capacity;
}

} 数组+链表实现 hashtable，支持扩容