dtpfia3334 2010-06-28 16:38
浏览 88


Recently I have read about hash-tables in a very famous book "Introduction to Algorithms". I haven't used them in any real applications yet, but want to. But I don't know how to start.
Can anyone give me some samples of using it, for example, how to realize a dictionary application (like ABBYY Lingvo) using hash-tables?
And finally I would like to know what is the difference between hash-tables and associative arrays in PHP, I mean which technology should I use and in which situations?
If I am wrong (I beg pardon) please correct me, because actually I am starting with hash-tables and I have just basic (theoretical) knowledge about them.
Thanks a lot.

  • 写回答

5条回答 默认 最新

  • dongzi4030 2010-06-28 16:40

    In PHP, associative arrays are implemented as hashtables, with a bit of extra functionality.

    However technically speaking, an associative array is not identical to a hashtable - it's simply implemented in part with a hashtable behind the scenes. Because most of its implementation is a hashtable, it can do everything a hashtable can - but it can do more, too.

    For example, you can loop through an associative array using a for loop, which you can't do with a hashtable.

    So while they're similar, an associative array can actually do a superset of what a hashtable can do - so they're not exactly the same thing. Think of it as hashtables plus extra functionality.

    Code examples:

    Using an associative array as a hashtable:

    $favoriteColor = array();
    echo 'bob likes: '.$favoriteColor['bob']."
    echo 'Sally likes: '.$favoriteColor['Sally']."
    //output: bob likes blue
    //        Sally likes pink

    Looping through an associative array:

    //up until here, we're using the array as a hashtable.
    //now we loop through the array - you can't do this with a hashtable:
    foreach($idTable as $person=>$id)
        echo 'id: '.$id.' | person: '.$person."
    //output: id: 1 | person: Tyler
    //        id: 20 | person: Bill
    //        id: 4 | person: Marc

    Note especially how in the second example, the order of each element is maintained (Tyler, Bill Marc) based on the order in which they were entered into the array. This is a major difference between associative arrays and hashtables. A hashtable maintains no connection between the items it holds, whereas a PHP associative array does (you can even sort a PHP associative array).

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
  • duanboxue3422 2010-06-28 16:39

    php arrays ARE basically hash tables

  • dongpo2014 2010-06-28 17:19

    An associative array is an array where you don't access elements by an index, but by a key. How this works internally is implementation specific (there is no rule how it must work). An associative array could be implemented by a hash table (most implementations will do that), but it could also be implemented by some sort of tree structure or a skip list or the algorithm just iterates over all elements in the array and looks for a key that matches (this would be awfully slow, but it works).

    A hash table is a way how to store data where values are associated to keys and where you intend to find values for keys within a (usually almost) constant time. This sounds exactly like what you expect of an associative array, that's why most of the time hash tables are used for implementing those arrays, but that is not mandatory.

  • duanpai9945 2010-06-28 17:36

    The difference between an associative array and a hash table is that an associative array is a data type, while a hash table is a data implementation. Obviously the associative array type is very important in many current programming languages: Perl, Python, PHP, etc. A hash table is the main way to implement an associative array, but not quite the only way. And associative arrays are the main use of hash tables, but not quite the only use. So it's not that they are the same, but if you already have associative arrays, then you usually shouldn't worry about the difference.

    For performance reasons, it can be important to know that your associative arrays in your favorite language are implemented as hashes. And it can be important to have some idea of the overhead cost of that implementation. Hash tables are slower and use more memory than linear arrays as you see them in C.

    Perl lumps the two concepts together by calling associative arrays "hashes". Like a number of features of Perl, it isn't quite wrong, but it's sloppy.

  • dounao5856 2012-03-13 08:57

    An array in PHP is actually an ordered map, not hashtable. Main difference between map and hashtable consists in inability to remember the order in wich elements have been added. On the other hand, hashtables are much faster than maps. Complexity of fetching an element from map is O(nlogn) and from hashtable is O(1).




  • ¥50 74LS系列 74LS00 74LS04设计一个RS485电路(关键词-差分)
  • ¥30 各位help写一下代码
  • ¥15 在运行SDEdit模型下载不了
  • ¥15 求51控制l298n驱动的小车中超声波避障怎么写
  • ¥15 电脑连上WIFI却用不了
  • ¥30 MATLAB在RLC电路的固有响应和阶跃响应GUI仿真报告
  • ¥15 hyper-v出现的问题
  • ¥15 有能用的可加酬金,求可以批量下载懒人听书的软件,能登录自己帐号的。
  • ¥100 高博一起做RGB-D SLAM(5)VO无法出visualisation问题
  • ¥15 使用matlab进行手眼标定的仿真验证,得到齐次矩阵与opencv相差较大