在Emacs Lisp中，如何获得单个散列键？

Question

我试图解决的问题是在非有向图中找到最少数量的子树，其中每个节点都在子树中。

我的算法如下：

make a hash as follows 
    key= each node, 
    value= all nodes directly accessible from the key node 
    if a node has no edges it still has a key/value pair in the hash 
    each edge will be represented twice, once each direction 
loop until hash is empty 
    get any hash key/value pair 
    save the value to the working-list 
    remove the key/value from the hash 
    in a loop until the working-list is empty 
    (when (gethash (car working-list) hash) 
     concatenate value to the end of the working-list 
     (remhash (car working-list) hash)) 
    (pop working-list) 
    When the loop is finished you have removed all nodes and edges in a single subtree from the hash. 
    Increment number of subtrees. 
end loop until the hash is empty. 
report number of subtrees 

下面的代码：

(defun count-subtrees (hash) 
; hash 
;  key= each node, 
;  value= all nodes directly accessible from the key node 
; if a node has no edges it still has a key/value pair in the hash 
; each edge will be represented twice, once each direction 

(let ((number-of-trees 0)) 
    (while (setf key (anykey-in-hash hash))  ; this is where I need any key in the hash 
    (setf working-list (gethash key hash)) 
    (remhash key hash) 
    (while (gethash (car working-list) hash) 
     (setf working-list (append working-list 
           (gethash (car working-list hash)))) 
     (remhash (car working-list) hash) 
     (pop working-list)) 
    (incf number-of-trees)) 
    number-of-trees)) 

我不想遍历键，我想只有一个。

备注：

谢谢大家的回复。我正在将这些评论引导给你。

编辑改变了我的问题，添加了“随机”一词。我不在乎它是否随机。回应：

(defun anykey-in-hash (hash-table) 
    (block nil 
     (maphash (lambda (k v) (return (values k v))) 

是一个完美的解决方案。

我无意中使用'while'（我从Paul Graham的书中得到）而没有定义它。我希望它不会让任何人感到困惑。

我也用setf代替let来定义变量。愚蠢的错误，我永远不会真的这样做。

最初我有一个所有键的列表。但在算法期间，键/值对被删除。这就是为什么我需要留下任何一个。

我也使用工作列表作为列表。工作列表包含子树中的一些节点。所有这些节点（以及他们的孩子*和他们孩子的孩子......）都需要从哈希中删除。追加到这个列表是为了简化代码。在实际的应用程序中，我会使用其他数据结构，可能是列表的列表。但我觉得这样做会增加复杂性，而不会增加任何问题的含义。

*当我说孩子，我的意思是使用节点作为散列的关键，值是一个孩子的列表。

Answer 1

您正在设置全局变量而未事先声明它们，这是不便携的，并且由于副作用通常不安全;喜欢让绑定。

至于获得“随机”键，你可以简单地实现anykey-in-hash这样的：

(defun anykey-in-hash (hash-table) 
    (block nil 
    (maphash (lambda (k v) (return (values k v))) 
      hash-table))) 

存储在哈希表元素的顺序取决于实施，使maphash将遍历条目中的任意（但可能是确定性的）订单。如果你真的需要一个随机的顺序，即一个顺序可以改变与不同的函数调用相同的参数，你必须收集的钥匙，并随机选择一个。

在你的例子中，似乎你只需要计算一次键的列表，而不是在while循环的每次迭代中。我亲自得到一个列表中的所有密钥，洗牌它一次，然后流行元素从它的需要。

我原来虽然代码是在Common Lisp中。在CL中，Alexandria library定义了shuffle（和random-elt）以及hash-table-keys（或hash-table-alist，如果您需要密钥和值）。

在Emacs Lisp中，您也可以使用maphash轻松实现hash-table-keys（您可以从maphash调用的函数内部将列表中的按键放在列表的前面）。如果您有Emacs 24.4，您可以(require 'subr-x)并致电get-hash-keys。可以像在CL中那样进行混洗，你可以使用亚历山大（https://gitlab.common-lisp.net/alexandria/alexandria/blob/master/sequences.lisp#L90）的算法，知道你只关心参数是列表的情况。