NV3

哈希表:搜索的有效手段介绍
当我曾经参与的电信顾问公司的路由优化软件的设计，所需的组件是为寻找最低成本路由机制沟通的网络站点之间的交通需求。换句话说，所有的电信运营商提供了最好的关税的有效手段。
有大量不同类型的电话路由的关税，无论是地理，地理，移动，保险费率，freefone，国际等，经常受到改变。关注的是创建一个代表电话号码字符串和其相关的关税之间的映射问题准确，快速的方式。
寻找大型网络上的数字成千上万的关税时，顺序搜索任何东西，但简单的例子是不切实际的商业成本最低的路由包。二进制搜索排序列表进行了调查，是一个很大的进步，给予了良好的业绩，即使在非常大的列表，类似于平均为O（log n）的。也有人意识到，哈希表查找最快的手段之一，通常在固定的时间为O（1）执行。关于哈希表
哈希表是一个软件的数据结构的基础上，使用一个索引查找表，显着加快映射的想法。鉴于电话数字通常代表字符串和数字表示的关税，我们不能直接使用字符串索引数组。相反，我们计算字符串的索引值使用一种特殊的散列函数，并使用该指数值访问数组，包含预先定义的关税，我们希望。世界上真正的散列
在现实中，完美的哈希是小于直接实现。通常发生的是哈希函数有时会映射到两个或两个以上的不同弦上相同的索引值，作为碰撞。为了解决这个问题，我们的哈希表需要映射到字符串链表的每一个潜在的选择，不只是一个单一的，因此，通过搜索挂钩的候选人名单，我们可以找到我们后，以及关税的价值，它包含的字符串。使用顺序搜索（循环）时，需要找到我们所追求的比较平均数是N / 2。当使用哈希表，平均数需要比较的是，加上一个哈希函数的计算。定义一个哈希表类
这是定义的类来实现的哈希表。哈希表本身就是一个链表的索引数组。这些链表大多将包含没有一个条目。当多个字符串散列相同的索引值发生碰撞时，该项目被添加到相同的链表通过新增的功能:

class HashTable

{

private:

    int hash( const char* str ) const;

    LinkedList list[ TableSize ];

    LinkedList const & FindList( const char* str ) const;



public:



    void Add( const char* str, int id );

    bool Get( const char* str, int& value );

};

// Return the linked list containing one or more items

LinkedList const & HashTable::FindList( const char* str ) const

{

    int h = hash( str );

    return list[ h ];

}