算法学习一，基础查找算法和排序算法
你提供的代码示例展示了两种常见的哈希表实现方法：拉链法（Separate Chaining）和线性探测法（Linear Probing）。每种方法都有其优缺点，适用于不同的场景。
拉链法（Separate Chaining）
拉链法通过将每个散列值对应的位置存储一个链表来解决冲突。这种方法的优点是简单且实现灵活，可以使用任何数据结构来存储冲突的键值对。以下是拉链法的主要特点：
优点：
- 简单且实现灵活。
- 不会像线性探测那样导致同类哈希的聚集。
缺点：
- 需要额外的空间来存储链表。
代码示例（使用拉链法）：
namespace StructScript { /// <summary> /// 哈希表的查找算法主要分为两步： /// 第一步是用哈希函数将键转换为数组的一个索引，理想情况下不同的键都能转换为不同的索引值，但是实际上会有多个键哈希到到相同索引值上。 /// 因此，第二步就是处理碰撞冲突的过程。这里有两种处理碰撞冲突的方法：separate chaining（拉链法）和linear probing（线性探测法）。 /// 拉链法： /// 使用链表来解决冲突 /// </summary> public class HashSearch2<T> { private int mCount = 16; // 线性探测表的大小 private List<T>[] mValues; public HashSearch2() { mValues = new List<T>[mCount]; for (int i = 0; i < mCount; i++) { mValues[i] = new List<T>(); } } private int HashCode(T value) { return (value.GetHashCode() & 0xFFFFFFF) % mCount; } public void Add(T value) { // 当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1 int index = HashCode(value); if (!mValues[index].Contains(value)) { mValues[index].Add(value); } } public bool Contains(T value) { // 当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1 int index = HashCode(value); return mValues[index].Contains(value); } } } 线性探测法（Linear Probing）
线性探测法通过在冲突发生时，直接检查散列表中的下一个位置来解决冲突。这种方法的优点是简单，但会形成聚集现象，导致后续插入和查找操作的性能下降。
优点：
- 实现简单。
缺点：
- 会导致同类哈希的聚集。
- 插入和查找操作在发生冲突时需要进行多次检查，性能下降。
代码示例（使用线性探测法）：
namespace StructScript { /// <summary> /// 哈希表的查找算法主要分为两步： /// 第一步是用哈希函数将键转换为数组的一个索引，理想情况下不同的键都能转换为不同的索引值，但是实际上会有多个键哈希到到相同索引值上。 /// 因此，第二步就是处理碰撞冲突的过程。这里有两种处理碰撞冲突的方法：separate chaining（拉链法）和linear probing（线性探测法）。 /// 线性探测法： /// 使用大小为M的数组来保存N个键值对,我们需要使用数组中的空位解决碰撞冲突 /// 当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1 /// 线性探测虽然简单，但是有一些问题，它会导致同类哈希的聚集。在存入的时候存在冲突，在查找的时候冲突依然存在 /// </summary> public class HashSearch2<T> { private int mCount = 16; // 线性探测表的大小 private T[] mValues; public HashSearch2() { mValues = new T[mCount]; } private int HashCode(T value) { return (value.GetHashCode() & 0xFFFFFFF) % mCount; } public void Add(T value) { // 当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1 for (int i = 0; i < mCount; i++) { int index = (HashCode(value) + i) % mCount; if (mValues[index] == null || mValues[index].Equals(default(T))) { mValues[index] = value; break; } } } public bool Contains(T value) { // 当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1 for (int i = 0; i < mCount; i++) { int index = (HashCode(value) + i) % mCount; if (mValues[index] != null && mValues[index].Equals(value)) { return true; } if (mValues[index] == null) { break; } } return false; } } } 总结
- 拉链法：通过链表解决冲突，简单且实现灵活，但需要额外的空间。
- 线性探测法：通过直接检查下一个位置解决冲突，实现简单但会导致聚集现象。
选择哪种方法取决于具体的应用场景和性能要求。如果对内存使用有较高要求，可以选择拉链法；如果对性能要求较高，可以考虑其他更复杂的哈希表实现方法，如双散列法（Double Hashing）或二次探测法（Quadratic Probing）。
