常用的数据结构

队列(FIFO)



栈(LIFO)



链表



hash表

  

• hash辩论处理惩罚
  
     
  
  • 开放式寻址
    
          
    
    • 线性探测
      
              
      
      • 表现依次查抄索引为 hash(key) + 1、hash(key) + 2 ... 的位置。        
        
      • i 是辩论后的探查步数。        
        
      • 公式：hash(i) = (hash(key) + i) % TableSize      
        
            
      
    • 二次探查
      
              
      
      • 规则：辩论后探查的步长是平方递增的，比方，查抄位置为 hash(key) + 1²、hash(key) + 2² 等。        
        
      • 公式：hash(i) = (hash(key) + i²) % TableSize      
        
            
      
    • 双重hash
      
              
      
      • 规则：采取第二个哈希函数来确定探查的步长。        
        
      • 公式：hash(i) = (hash1(key) + i * hash2(key)) % TableSize
        
                 
        
        • hash1(key) 是主哈希函数。         
          
        • hash2(key) 是辅助哈希函数，通常选择 hash2(key) = 1 + (key % (TableSize - 1))，确保探查步长不为零。         
          
              
        
           
      
       
    
  • 利用链表