文章目錄
- 樹
- Question One： 請你回答一下map和unordered_map優點和缺點
- Question Two：請你回答一下epoll怎么實作的
- 堆與堆疊
- Question Three： 請你來說一下堆和堆疊的區別
本篇是資料結構和演算法相關，
如果基礎不太行的朋友建議先：
“為實習準備的資料結構” 系列 – 導航篇
演算法集錦 – 導航篇
樹
Question One： 請你回答一下map和unordered_map優點和缺點
對于map，其底層是基于紅黑樹實作的，優點如下：
1)有序性，這是map結構最大的優點，其元素的有序性在很多應用中都會簡化很多的操作
2)map的查找、洗掉、增加等一系列操作時間復雜度穩定，都為logn
缺點如下：
1）查找、洗掉、增加等操作平均時間復雜度較慢，與n相關
對于unordered_map來說，其底層是一個哈希表，優點如下：
查找、洗掉、添加的速度快，時間復雜度為常數級O(1)
缺點如下：
因為unordered_map內部基于哈希表，以（key,value）對的形式存盤，因此空間占用率高
Unordered_map的查找、洗掉、添加的時間復雜度不穩定，平均為O(1)，取決于哈希函式，極端情況下可能為O(n)
Question Two：請你回答一下epoll怎么實作的
Linux epoll機制是通過紅黑樹和雙向鏈表實作的，
首先通過epoll_create()系統呼叫在內核中創建一個eventpoll型別的句柄，其中包括紅黑樹根節點和雙向鏈表頭節點，然后通過epoll_ctl()系統呼叫，向epoll物件的紅黑樹結構中添加、洗掉、修改感興趣的事件，回傳0標識成功，回傳-1表示失敗，最后通過epoll_wait()系統呼叫判斷雙向鏈表是否為空，如果為空則阻塞，
當檔案描述符狀態改變，fd上的回呼函式被呼叫，該函式將fd加入到雙向鏈表中，此時epoll_wait函式被喚醒，回傳就緒好的事件，
堆與堆疊
Question Three： 請你來說一下堆和堆疊的區別
1）申請方式：
堆疊由系統自動分配和管理，堆由程式員手動分配和管理，
2）效率：
堆疊由系統分配，速度快，不會有記憶體碎片，
堆由程式員分配，速度較慢，可能由于操作不當產生記憶體碎片，
3）擴展方向
堆疊從高地址向低地址進行擴展，堆由低地址向高地址進行擴展，
4）程式區域變數是使用的堆疊空間，new/malloc動態申請的記憶體是堆空間，函式呼叫時會進行形參和回傳值的壓堆疊出堆疊，也是用的堆疊空間，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/266709.html
標籤：其他