如何看待某國內大公司Python面試題，有關dict中初始化為固定值？

02-26

閱讀下面的代碼，寫出A0，A1至A6的最終值。
A0 = dict(zip((a,b,c,d,e),(1,2,3,4,5))) A1 = range(10) A2 = [i for i in A1 if i in A0] A3 = [A0[s] for s in A0] A4 = [i for i in A1 if i in A3] A5 = {i:i*i for i in A1} A6 = [[i,i*i] for i in A1]
答案在這裡： A0 = {a: 1, c: 3, b: 2, e: 5, d: 4} A1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] A2 = [] A3 = [1, 3, 2, 5, 4] A4 = [1, 2, 3, 4, 5] A5 = {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81} A6 = [[0, 0], [1, 1], [2, 4], [3, 9], [4, 16], [5, 25], [6, 36], [7, 49], [8, 64], [9, 81]]
請給出為什麼A3= [1, 3, 2, 5, 4] 的理由，即A0初始化為什麼為固定值

這個是根據Python2.X的dict的源碼來實現的，主要是 PyDict_SetItem()這個函數，在字典裡面添加一個項的步驟是，先對key求hash值，之後hash值與掩碼mask做操作，得到哈希表中空位置(slot),如果該位置未被佔用，那key的槽就是它了，否則根據開放定址繼續尋找。因此輸出的key的順序就是在哈希表中的順序，為什麼是13254的原因如下:

ln [16]: hash(a) 7
Out[16]: 0

In [18]: hash(b) 7
Out[18]: 3

In [19]: hash(c) 7
Out[19]: 2

In [20]: hash(d) 7
Out[20]: 5
In [21]: hash(e) 7
Out[21]: 4

按照在哈希表中的順序就是: acbed, 對應到題目就是13254.

ps: 為什麼7 是因為初始默認大小是8:

#define PyDict_MINSIZE 8 ,
掩碼mask=size-1，即:8-1 = 7.

如果元素個數超過了當前size的 2/3了，就會重新擴展。

如果 A3 你回答 [1, 2, 3, 4, 5] ，面試官說不對，必須是 [1, 3, 2, 5, 4] 的話，這家公司不要去。如果面試官說答案不一定的話，可以考慮去。

如果面試官說，雖然答案不一定，但是 python 3.6 的實現里，一定是 [1, 2, 3, 4, 5]，但是別先依賴這個，未來可能會用語言規範的方式確定下來，也可能去掉這個 feature ，那麼，可以認真的考慮去。

當然，把簡歷發給我也是一個不錯的選擇

這個題目就是錯的，dict數據結構本身就不保證有序，你換個python版本順序就完全變了。

正如js對象的key－value也不保證有序，但V8的實現恰好是按插入順序的，如果依賴這個特性，換個瀏覽器程序直接就掛了。

我曾經見過某公司的某個關鍵程序用Java 6的HashMap輸出的key的順序作為業務邏輯，結果升級Java 8直接掛了，因為Java 8改了HashMap的實現。

dict／map這種數據結構本身就是一種不保證順序的協議，寫程序不按照協議來寫，而是按照某個版本的特定實現來寫，這不有病嗎？

A3這個，你只要回答「dict是hash表實現，所以具體輸出和hash表的實現方式相關」就可以了，如果面試官一定要一個確定結果，那你可以走人，但這種題目也可能在故意考驗你，所以不偏不倚回答是最好的

這莫非是傳說中的譚浩強教你學Python

嗯，我也曾經喜歡糾結於這些實現細節問題，比如C里的 printf 列印順序是從右到左，++i 比 i++更快等等。

掌握這些知識的確很讓人亦可賽艇，然而並沒有什麼卵用。說白了，這都是應試教育的鍋，總覺得學會了一個個奇技淫巧，就能比別人更牛逼。

而對於 Python 來說，這些細節甚至不如熟練使用基本庫重要。列表推導字典推導玩熟了嗎？coroutine 玩熟了嗎？yield 玩熟了嗎？各種設計模式在 Python 中更優雅的實現學會了嗎？

跑題了，不過還是建議題主不要糾結這種問題，沒有任何意義。

你的問題的標題「有關dict中內存分布問題？」和下面最後「請給出為什麼A3= [1, 3, 2, 5, 4] 的理由」問題描述不一致？？？？？

建議看看

從Python官方文檔中挖礦之List Comprehensions - 知乎專欄

用到的語法形式是

for key in d 按照key 取值 d[key]

Python2 字典的本質是hash表
hash表的數據結構，無序。

Python3.6 字典已經是有序了。

茴香豆的回有幾種寫法？這種鑽牛角尖的特點就是中國碼農的悲哀，把心思放在這些事情上面註定一生達不到某種境界

關於python中dict實現傳送一篇譯文：深入 Python 字典的內部實現 - Python - 伯樂在線

Python 中的hash還是挺複雜的，看看源碼(刪除了一些細節）：

版本是 Python2.7.11

// stringobject.c static long string_hash(PyStringObject *a) { register Py_ssize_t len; register unsigned char *p; register long x;


  len = Py_SIZE(a);
  if (len == 0) {

    a-&>ob_shash = 0;

    return 0;

  }

  p = (unsigned char *)a-&>ob_sval;

  x = _Py_HashSecret.prefix; // 這個比較奇怪

  x ^= *p &<&< 7;
  while (--len &>= 0)

    x = (1000003 * x) ^ *p++;

  x ^= Py_SIZE(a);

  x ^= _Py_HashSecret.suffix; // 奇怪+1

 // 其他的都是正常的hash

  return x;

}

// random.c

typedef struct {

  long prefix;

  long suffix;

} _Py_HashSecret_t;

_Py_HashSecret_t _Py_HashSecret; // 也就是一個結構體

// 那這個結構體是怎麼初始化的

void _PyRandom_Init(void)

{

  char *env;

  void *secret = _Py_HashSecret;

  Py_ssize_t secret_size = sizeof(_Py_HashSecret_t);

if (!Py_HashRandomizationFlag) { // 禁用隨機哈希 memset(secret, 0, secret_size); return; } // 後面就是對這個結構體隨機初始化，也就是啟用了隨機哈希 } // 現在關鍵就是Py_HashRandomizationFlag了，這是一個int // main.c Py_Main switch (c) { // c 是命令行參數，python -R case R: Py_HashRandomizationFlag++; break; } if ((p = Py_GETENV("PYTHONHASHSEED")) *p != ) // 如果設置這個環境變數為任意值 Py_HashRandomizationFlag = 1; // 如果設置PYTHONHASHSEED為一個數字，就會以這個數字為隨機種子，最後結果還是固定的， //設置成其他值就會調用操作系統相關的隨機函數了

所以當沒有命令行參數-R，或者沒有設置環境變數PYTHONHASHSEED的時候，hash的結果就是固定的，否則就是隨機的。

如果是考核「Python中字典是無序的」，那沒什麼問題，但是如果考核的是「這幾個字元串在Python的字典中的順序」，那就不合適了（你可以用這個懟他 (?￣▽￣)?。

你如果看得懂A0是個dict，我想不到理由你看不懂A3...

Modern Dictionaries by Raymond Hettinger

https://dl.dropboxusercontent.com/u/3967849/sfmu2/_build/html/goal.html

用代碼看，在 Python 3.6， dict = Orderdict

因為字典是不保證順序的？保證順序要用集合庫中的順序字典？

挺基礎的題目，分歧比較大的估計是A3的值吧。

按照python3文檔的說法，dictionary是無序的，所以用for...in...的時候返回key的順序和實現相關，所以A3應該任何順序都是有可能的。考慮代碼穩固性，應該用：

for k in sorted(A3.keys())

這個順序和版本有關,我曾經以為Python對dict的排序有問題,直到看到它的源代碼,真是認輸.所以用這個當面試題,是測試被面試者對Python Dict的代碼實現,也就是了解被面試者是否讀過Python源代碼,或者是否熟練編程,熟悉Python中常見的Python "暗坑".問題不算錯,但是這個屬於未來版本需要改善的問題,一般我們基本處於閉嘴的情況,不說,不做.坐等改善就夠了.

依賴語言實現特性來拿到一個值，從技術角度上說，得知道，但所有的業務代碼，是應該依賴於規則，依賴於實現，過兩年就要哭了。

跟考官聊聊啥叫 OrderedDict

8.3. collections - High-performance container datatypes - Python 2.7.13 documentation

只有我關心是什麼公司嗎逃。另外我們公司(appannie也在招後端，優秀的pythoner們，簡歷砸過來

Hash key值是沒有順序的

hash table 跟順序有啥關係

「確定dict中key的順序」：從這個需求出發的話，就是說某工程中有個數據結構dict，而某一操作或者事務需要依賴該順序。
而dict是可變類型，pop操作和update操作都可能會導致key的順序變化，那該操作就有隱藏風險，這個時候，為何不用OrderDict甚至list

以工程角度看待該問題，可能有些偏離主題了。

感覺排列有點像堆的演算法