我正在使用C语言编写哈希表,我正在测试字符串的哈希函数.

我尝试过的第一个函数是添加ascii代码并使用modulo(%100)但是我在第一次数据测试时得到的结果很差:140个单词的40个冲突.

最终的输入数据将包含8 000个单词(它是一个文件中的dictionnary存储).哈希表声明为int table [10000]并包含txt文件中单词的位置.

第一个问题是哪个是散列字符串的最佳算法？以及如何确定哈希表的大小？

提前致谢 !

:-)

该djb2算法对字符串的哈希函数.

unsigned long hash = 5381;
int c;

while (c = *str++)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

为什么5381和33如此重要？

如果您对Mongolian的细节不感兴趣,但只想快速回答有关在Swift中使用和转换Unicode值的问题,请跳到接受答案的第一部分.

背景

我想渲染传统蒙古语的 Unicode文本,以便在iOS应用程序中使用.更好和长期的解决方案是使用AAT智能字体来渲染这个复杂的脚本.(这些字体确实存在,但它们的许可证不允许修改和非个人使用.)但是,由于我从未制作过字体,更不用说AAT字体的所有渲染逻辑了,我只是打算自己进行渲染.斯威夫特现在.也许在以后我可以学习制作智能字体.

在外部我将使用Unicode文本,但在内部(在a中显示UITextView)我将Unicode转换为以哑字体存储的单个字形(用Unicode PUA值编码).所以我的渲染引擎需要将蒙古语Unicode值(范围:U + 1820到U + 1842)转换为存储在PUA中的字形值(范围:U + E360到U + E5CF).无论如何,这是我的计划,因为它是我过去在Java中所做的,但也许我需要改变我的整个思维方式.

例

下图显示su在蒙古语中使用两种不同形式的字母u(红色)两次写入.(蒙古文是垂直书写的,字母连接像英文草书一样.)

在Unicode中,这两个字符串将表示为

var suForm1: String = "\u{1830}\u{1826}"
var suForm2: String = "\u{1830}\u{1826}\u{180B}"

自由变量选择器(U + 180B)in suForm2被Swift识别(正确)String为与其前面的u(U + 1826)的单位.Swift认为它是一个单一的字符,一个扩展的字形集群.但是,为了自己进行渲染,我需要将u(U + 1826)和FVS1(U + 180B)区分为两个不同的UTF-16代码点.

出于内部显示的目的,我将上述Unicode字符串转换为以下呈现的字形字符串:

suForm1 = "\u{E46F}\u{E3BA}" 
suForm2 = "\u{E46F}\u{E3BB}"

题

我一直在玩Swift String和Character.关于它们有很多方便的东西,但是因为在我的特殊情况下我只使用UTF-16代码单元,我想知道我是否应该使用旧的NSString而不是Swift的String.我意识到我可以String.utf16 …

在Objective-C(和其他语言)中,一个相对较好的默认实现- (NSUInteger)hash可能是:

- (NSUInteger)hash {
   return 31u * [self.property1 hash] + [self.property2 hash];
}

假设两个property1并property2返回良好的值hash.

这在Swift var hashValue: Int在其Hashable协议上定义的等效方法中不起作用.

等效的Swift代码可能会溢出,这是Swift中的运行时错误.

var hashValue: Int {
    return 31 * property1.hashValue + property2.hashValue // overflow-tastic
}

所以我的问题是,在Swift中生成哈希值(实现Hashable)的最佳技术是什么？我应该使用XOR吗？虽然我的理解是XOR不是创建统一哈希分布的理想选择.也许更奇特的东西？

TLDR

我的自定义结构实现了Hashable Protocol.但是,当在a中插入密钥时发生散列冲突时Dictionary,它们不会自动处理.我该如何克服这个问题？

背景

我之前曾问过这个问题 如何在Swift中为Int数组(自定义字符串结构)实现Hashable Protocol.后来我添加了自己的答案,这似乎有效.

但是,最近我hashValue在使用a时发现了碰撞的微妙问题Dictionary.

最基本的例子

我尽可能地将代码简化为以下示例.

定制结构

struct MyStructure: Hashable {

    var id: Int

    init(id: Int) {
        self.id = id
    }

    var hashValue: Int {
        get {
            // contrived to produce a hashValue collision for id=1 and id=2
            if id == 1 {
                return 2 
            }
            return id
        }
    }
}

func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
    return lhs.hashValue == rhs.hashValue
}

请注意全局函数重载相等运算符(==)以符合 …

为了解决这个问题,我一直在玩一个实现Hashable Protocol的自定义结构.我正在尝试查看等效运算符overload(==)被调用多少次,具体取决于填充a时是否存在哈希冲突Dictionary.

更新

@matt编写了一个更清晰的自定义结构示例,该结构实现了Hashable协议并显示了调用的频率hashValue和==调用次数.我在下面复制他的代码.要查看我的原始示例,请查看编辑历史记录.

struct S : Hashable {
    static func ==(lhs:S,rhs:S) -> Bool {
        print("called == for", lhs.id, rhs.id)
        return lhs.id == rhs.id
    }
    let id : Int
    var hashValue : Int {
        print("called hashValue for", self.id)
        return self.id
    }
    init(_ id:Int) {self.id = id}
}
var s = Set<S>()
for i in 1...5 {
    print("inserting", i)
    s.insert(S(i))
}

这会产生结果:

/*
inserting 1
called …

我最近了解了一些有关散列值的知识，因此也听说了有关散列冲突的问题。
因此，我想知道：一个人该如何处理？

例如，Swift的Dictonary键使用哈希值。我假设它通过哈希查找其值。那么Swift如何Dictionary存储恰好具有相同哈希值的不同键的值呢？

我想对xy网格中的坐标对元素进行集合运算.例如{(0,0),(1,4),(1,5),(2,3)}与{(2,3),(1,4),(2,6)} = {( 0,0),(1,4),(1,5),(2,3),(2,6)}遗憾的是我无法找到一种将元组插入Swift的Set命令的方法,因为它说它们是不符合'hashable'协议.我相信我有一个解决方法,但它涉及很多代码.在我碰到磨刀石之前,有没有一种简单的方法让我失踪？

我是iOS框架的新手,所以我目前正在尝试在Swift中做所有事情.这可能是我的问题......

我正在过滤一个数组，该数组可以具有一个值，其中有多个具有相同名称的模型，只是它们具有不同的模型编号。

变数

var modelArray = [model]()

结构

struct model {
    var modelName = String();
    var modelNumber = String();
    var manufacturer = String();
    var phiTypeCode = String();
    var phiTypeDesc = String();
}

过滤

var filteredArray = self.modelArray.filter { $0.manufacturer.range(of: manufacturerVar, options: .caseInsensitive) != nil }

仅由于存在具有不同型号的相似型号的可能性，这会产生正确的过滤Array，我正尝试从中删除重复项filteredArray。相当新，我没有太多的经验可以使结构可哈希化以使用建议的解决方案。

希望这更清楚