ビットマップを使ったビット単位のトライ

long bitMap = mem [ nodeIdx ] ; long bitPos = 1L << value ; // 6 ビット値if (( bitMap & bitPos ) == 0 ) return false ; // 見つかりませんlong childNodeIdx = mem [ nodeIdx + 1 + Long . bitCount ( bitMap & ( bitPos - 1 )) ] ;   
     	
      
	  
           

int bitCount ( long x ) x -= (( x >>> 1 ) & 0x5555555555555555L ); x = ( x & 0x33333333333333333L ) + (( x >>> 2 ) & 0x3333333333333333L ); x = ( x + ( x >>> 4 )) & 0x0f0f0f0f0f0f0f0fL ; x += ( x >>> 8 ); x += ( x >>> 16 ); x += ( x >>> 32 ); return x & 0x7f ;  
	      
	          
	        
	    
	    
	    
	   

パブリッククラスBBTrieSet {   

    long [] mem ; long [] freeLists ; long freeIdx ; 
     
     

    長いルート;長いカウント; 
     

    // 配列はゼロベースなので、最大ノード サイズは 1 (ビットマップ) + 64 (子ポインターまたはリーフ値) + 1 です
。final static int FREE_LIST_SIZE = 1 + 64 + 1 ;         

    最終的な静的int KNOWN_EMPTY_NODE = 0 ;最終的な静的int KNOWN_DELETED_NODE = 1 ;最終的な静的int HEADER_SIZE = 2 ; // KNOWN_EMPTY_NODE、KNOWN_DELETED_NODE     
         
          

    public BBTrieSet ( int size ) { mem = new long [ size ] ; freeLists = new long [ FREE_LIST_SIZE ] ; freeIdx = HEADER_SIZE ; root = KNOWN_EMPTY_NODE ; count = 0 ; }   
           
           
          
          
          
    

    private long allocate ( int size ) { long free = freeLists [ size ] ; if ( free != 0 ) { // 要求されたサイズはフリーリストで使用可能です。再リンクしてヘッドを返します。freeLists [ size ] = mem [ ( int ) free ] ; return free ; } else { // 拡張が必要か? if ( freeIdx + size > mem . length ) { // 25% 増やして、これで十分であることを確認します。int currSize = mem . length ; int newSize = currSize + Math . max ( currSize / 4 , size ); mem = Arrays . copyOf ( mem , newSize ); }    
           
            
            
               
             
        
         
            
                  
                
                   
                        
                   
            

            long idx = freeIdx ; freeIdx += size ; return idx ; } }   
              
             
        
    

    プライベートlong allocateInsert ( long nodeIdx 、int size 、int childIdx ) { long newNodeRef = allocate ( size + 1 );        
             

        int a = ( int ) newNodeRef ; int b = ( int ) nodeIdx ;    
            

        // 子のギャップ付きコピー
for ( int j = 0 ; j < childIdx ; j ++ ) mem [ a ++] = mem [ b ++] ; a ++ ; // 挿入for ( int j = childIdx ; j < size ; j ++ ) mem [ a ++] = mem [ b ++] ;                
              
         
                
              

        deallocate ( nodeIdx , size ); 

        newNodeRefを返します。} private long allocateDelete ( long nodeIdx 、int size 、int childIdx ) { long newNodeRef = allocate ( size - 1 ); 
    
    
            
             

        // 子要素を削除してコピー
int a = ( int ) newNodeRef ; int b = ( int ) nodeIdx ; for ( int j = 0 ; j < childIdx ; j ++ ) mem [ a ++ ] = mem [ b ++] ; b ++ ; // 削除for ( int j = childIdx + 1 ; j < size ; j ++ ) mem [ a ++] = mem [ b ++] ; deallocate ( nodeIdx , size );            
            
                
              
         
                  
              
        
         

        newNodeRefを返します。 
    

    private void deallocate ( long idx , int size ) { if ( idx == KNOWN_EMPTY_NODE ) return ; // 既知の空ノードを保持する      
           
             

        // フリーリストの先頭に追加
mem [ ( int ) idx ] = freeLists [ size ] ; freeLists [ size ] = idx ; }           
          
    

    private long createLeaf ( byte [] key , int off , int len ) { long newNodeRef = allocate ( 2 ); int a = ( int ) newNodeRef ; mem [ a ++] = 1L << key [ len - 2 ] ; mem [ a ] = 1L << key [ len - 1 ] ; // value len -= 3 ; while ( len >= off ) { long newParentNodeRef = allocate ( 2 ); a = ( int ) newParentNodeRef ; mem [ a ++] = 1L << key [ len --] ; mem [ a ] = newNodeRef ; newNodeRef = newParentNodeRef ; } return newNodeRef ; }        
           
            
              
               
          
            
               
               
                
              
              
        
         
    

    private long insertChild ( long nodeRef , long bitMap , long bitPos , int idx , long value ) { int size = Long . bitCount ( bitMap ); long newNodeRef = allocateInsert ( nodeRef , size + 1 , idx + 1 ); mem [ ( int ) newNodeRef ] = bitMap | bitPos ; mem [ ( int ) newNodeRef + 1 + idx ] = value ; return newNodeRef ; } private long removeChild ( long nodeRef , long bitMap , long bitPos , int idx ) { int size = Long . bitCount ( bitMap ); if ( size > 1 ) { // ノードにはまだ他の子/葉がありますlong newNodeRef = allocateDelete ( nodeRef , size + 1 , idx + 1 ); mem [ ( int ) newNodeRef ] = bitMap & ~ bitPos ; return newNodeRef ; } else { // ノードは空になったので削除しますdeallocate ( nodeRef , size + 1 ); return KNOWN_DELETED_NODE ; } }            
           
                 
             
                          
         
    
    
              
           
            
            
                     
                 
             
        
         
            
               
             
        
    

    パブリックlong size () {戻り値 count ; }   
         
    

}

    public boolean get ( byte [] key , int len ) { if ( root == KNOWN_EMPTY_NODE ) return false ;      
           
             

        long nodeRef = root ; int off = 0 ; for (;;) { long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // ++ に注意してください         if (( bitMap & bitPos ) == 0 ) return false ; // 見つかりません   
           
        
          
                
                  
                  
                  

            long値= mem [ ( int ) nodeRef + 1 + Long . bitCount ( bitMap & ( bitPos - 1 )) ] ;            

            if ( off == len - 1 ) { // リーフlong bitPosLeaf = 1L << key [ off ] ; return (( value & bitPosLeaf ) != 0 ); } else { // 子ポインターnodeRef = value ; } } }      
                
                     
                     
            
             
                
                  
            
        
    

    public boolean set ( byte [] key , int len ) { long nodeRef = set ( root , key , 0 , len ); if ( nodeRef != KNOWN_EMPTY_NODE ) { // 変更カウントを示します++ ; root = nodeRef ; return true ; } else return false ; }      
              
            
            
            
              
             
        
        
             
    

    private long set ( long nodeRef , byte [] key , int off , int len ) { long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // ++ に注意してくださいint idx = Long . bitCount ( bitMap & ( bitPos - 1 ) );          
            
              
                

        if (( bitMap & bitPos ) == 0 ) { // 子はまだ存在しませんlong value ; if ( off == len - 1 ) value = 1L << key [ off ] ; else value = createLeaf ( key , off , len ); return insertChild ( nodeRef , bitMap , bitPos , idx , value ); } else { // 子が存在しますlong value = mem [ ( int ) nodeRef + 1 + idx ] ; if ( off == len - 1 ) { //リーフにありますlong bitPosLeaf = 1L << key [ off ] ; if (( value & bitPosLeaf ) == 0 ) { // リーフの bitMap を更新しますmem [ ( int ) nodeRef + 1 + idx ] = value | bitPosLeaf ; return nodeRef ; } else // キーが既に存在しますreturn KNOWN_EMPTY_NODE ; } else { // リーフではない、再帰long childNodeRef = value ; long newChildNodeRef = set ( childNodeRef , key , off , len ); if ( newChildNodeRef == KNOWN_EMPTY_NODE ) return KNOWN_EMPTY_NODE ; if ( newChildNodeRef != childNodeRef ) mem [ ( int ) nodeRef + 1 + idx ] =      
            
             
                 
                    
            
                    
                 
        
         
            
                    
                  
                
                     
                      
                    
                             
                     
                
                
                    
                     
            
             
                
                   
                      
                   
                     
                   
                           newChildNodeRef ; 
nodeRefを返します。} } }                                 
            
        
    

    public boolean clear ( byte [] key , int len ) { long nodeRef = clear ( root , key , 0 , len ); if ( nodeRef != KNOWN_EMPTY_NODE ) { count -- ; if ( nodeRef == KNOWN_DELETED_NODE ) root = KNOWN_EMPTY_NODE ; else root = nodeRef ; return true ; } else return false ; }      
              
            
            
               
                  
            
                  
             
        
        
             
    

    パブリックlong clear ( long nodeRef 、byte [] key 、int off 、int len ) { if ( root == KNOWN_EMPTY_NODE ) return KNOWN_EMPTY_NODE ;          
           
             

        long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // ++ に注意してくださいif (( bitMap & bitPos ) == 0 ) { // 子要素が存在せず、キーが見つかりませんreturn KNOWN_EMPTY_NODE ; } else { // 子要素が存在しますint idx = Long . bitCount ( bitMap & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ; if ( off == len - 1 ) { // リーフにありますlong bitPosLeaf = 1L << key [ off ] ; if (( value & bitPosLeaf ) == 0 ) // キーが存在しませんreturn KNOWN_EMPTY_NODE ; else { // リーフのビットをクリアしますvalue = value & ~ bitPosLeaf ; if ( value != 0 ) { // リーフにはまだいくつかのビットが設定されているため、リーフを保持して更新しますmem [ ( int ) nodeRef + 1 + idx ] = value ; return nodeRef ; } else return removeChild ( nodeRef , bitMap , bitPosLeaf , idx ); } } else { // リーフではありませんlong childNodeRef = value ; long newChildNodeRef = clear ( childNodeRef , key , off , len ); if ( newChildNodeRef ==    
              
              
            
             
        
         
            
                   
                    
                  
                
                     
                     
                    
                     
                 
                    
                        
                        
                        
                               
                         
                    
                    
                            
                
            
             
                
                   
                      
                   KNOWN_EMPTY_NODE )
を返しますKNOWN_EMPTY_NODE 。if ( newChildNodeRef == KNOWN_DELETED_NODE )を返しますremoveChild ( nodeRef 、bitMap 、bitPos 、idx ) 。if ( newChildNodeRef != childNodeRef ) mem [ ( int ) nodeRef + 1 + idx ] = newChildNodeRef 。return nodeRef 。} } }                     
                   
                        
                   
                           
                                 
            
        
    

}

パブリックインターフェースBBTrieNode {パブリックlong getBitMap ();パブリックlong getBitMapLeaf ( long bitPos );パブリックBBTrieNode getChildNode ( long bitPos ); }パブリック静的クラスBBTrieNodeMem はBBTrieNodeを実装します{   
      
       
        

    
      

    長いノード参照;長い[]メモリ; 
     

    BBTrieNodeMem子; 

    パブリックBBTrieNodeMem ( long nodeRef 、long [ ] mem ) { this.nodeRef = nodeRef ; this.mem = mem ; }​​​     
          
          
    

    @Override 
public long getBitMap () { return mem [ ( int ) nodeRef ] ; }       
          
    

    @Override 
public long getBitMapLeaf ( long bitPos ) { int idx = Long . bitCount ( getBitMap () & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ;戻り値; }        
               
                
         
    

    @Override 
public BBTrieNode getChildNode ( long bitPos ) { int idx = Long . bitCount ( getBitMap () & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ; return new BBTrieNodeMem ( value , mem ); } }