拉鏈法是解決Hash沖突問題的方法之一,把所有hash值相同的元素鏈接在同一個單鏈表中。這也是jdk中hashmap,hashtable的實現方 式。外部拉鏈法的缺點是:它需要稍微多一些的空間來實現,因為添加任何元素都需要添加指向節點的指針,并且每次探查也要花費稍微多一點的時間,因為它需要 間接引用逐一查找匹配,而不是直接訪問元素。當大量相同hash值的元素保存時,就會導致鏈表巨長無比,這時get出對應元素時要在鏈表里比對key是否 相同直到找到對應的元素。
在多數web容器的設計中,request都是依靠相應語言的hashtable/hashmap實現,當不同的key存入時如果hash值相等則以鏈表 方式連接。此漏洞利用碰撞相同的hash值得到一個長鏈表,容器從request重新get時,map的計算過程會將時間復雜度巨增,原來一個簡單的過程 將變成一個很費cpu的過程。
解決辦法:限制最大請求body大小,限制請求的參數個數