了解传奇算法，先从哈希表开始

萧山财神

哈希表（Hash Table）是一种常用的数据结构，它通过键值对的方式存储数据，并使用哈希函数将键映射到存储桶（bucket）中，以实现快速的查找、插入和删除操作。Lua 本身已经内置了哈希表（即 Lua 的 table），但我们可以通过实现一个简单的哈希表来理解其工作原理。

下面是一个用 Lua 编写的简单哈希表实现示例：

哈希表实现

-- 定义哈希表类
HashTable = {}
HashTable.__index = HashTable

function HashTable:new(size)
    local ht = {
        size = size or 16,
        buckets = {}
    }
    for i = 1, ht.size do
        ht.buckets[i] = {}
    end
    setmetatable(ht, HashTable)
    return ht
end

-- 简单的哈希函数
function HashTable:hash(key)
    local hash = 0
    for i = 1, #key do
        hash = (hash * 31 + string.byte(key, i)) % self.size
    end
    return hash + 1
end

-- 插入键值对
function HashTable:insert(key, value)
    local index = self:hash(key)
    local bucket = self.buckets[index]
    for i, pair in ipairs(bucket) do
        if pair[1] == key then
            pair[2] = value
            return
        end
    end
    table.insert(bucket, {key, value})
end

-- 查找值
function HashTable:find(key)
    local index = self:hash(key)
    local bucket = self.buckets[index]
    for i, pair in ipairs(bucket) do
        if pair[1] == key then
            return pair[2]
        end
    end
    return nil
end

-- 删除键值对
function HashTable:remove(key)
    local index = self:hash(key)
    local bucket = self.buckets[index]
    for i, pair in ipairs(bucket) do
        if pair[1] == key then
            table.remove(bucket, i)
            return true
        end
    end
    return false
end

-- 测试哈希表
local ht = HashTable:new(16)

ht:insert("name", "Alice")
ht:insert("age", 30)
ht:insert("city", "New York")

print("查找键 'name':", ht:find("name"))  -- 输出: Alice
print("查找键 'age':", ht:find("age"))    -- 输出: 30
print("查找键 'city':", ht:find("city"))  -- 输出: New York

ht:remove("age")
print("查找键 'age' (删除后):", ht:find("age"))  -- 输出: nil

解释

1. HashTable类：定义了哈希表类，包含哈希表的大小和存储桶数组。

   • new 方法：创建一个新的哈希表实例，接受哈希表的大小作为参数，并初始化存储桶数组。
   • hash 方法：简单的哈希函数，将键映射到存储桶索引。
   • insert 方法：插入键值对，如果键已存在则更新其值。
   • find 方法：查找键对应的值，如果键不存在则返回 nil。
   • remove 方法：删除键值对，如果键存在则删除并返回 true，否则返回 false。

2. 测试代码：创建一个哈希表实例，插入一些键值对，查找和删除键值对，并输出结果。

输出

运行上述代码将输出以下内容：

查找键 'name': Alice
查找键 'age': 30
查找键 'city': New York
查找键 'age' (删除后): nil

这个简单的哈希表实现可以根据实际需求进行调整，例如使用更复杂的哈希函数、处理哈希冲突（如链地址法或开放地址法）等。通过合理的哈希表算法，可以实现高效的数据存储和查找操作。

复制粘贴就是干

为啥都没人回复

fightlee170017

讲到算法怎么少的了二分查找,咱们经常要遍历目标table,检索target,如果是array类型的table那么使用二分查找尤为方便.

-- 二分查找函数
function binary_search(arr, target)
    local left, right = 1, #arr

    while left <= right do
        local mid = math.floor((left + right) / 2)

        -- 检查中间元素是否是目标值
        if arr[mid] == target then
            return mid
        -- 如果目标在左半部分，则缩小右边界
        elseif arr[mid] > target then
            right = mid - 1
        -- 如果目标在右半部分，则缩小左边界
        else
            left = mid + 1
        end
    end

    -- 如果没有找到目标值，返回 -1 表示不存在
    return -1
end

-- 示例用法
local arr = {1, 3, 5, 7, 9, 11, 13, 15, 17}
local target = 9
local result = binary_search(arr, target)

if result ~= -1 then
    print(string.format("目标值 %d 在数组中的索引为 %d", target, result))
else
    print(string.format("目标值 %d 不在数组中", target))
end

唯一要注意的就是,接受的table需要是一个有序数组.

萧山财神

fightlee170017 发表于 2024-7-9 14:22
[md]讲到算法怎么少的了二分查找,咱们经常要遍历目标table,检索target,如果是array类型的table那么使用二分 ...

卧槽，牛逼