Try to detect the best partitioning strategy for a large bucket

    Consider nested buckets with common prefixes, and flat buckets.
967683
def detect_partition_strategy(bid, delimiters=('/', '-'), prefix=''):
    
    account, bucket = bid.split(":", 1)
    region = connection.hget('bucket-regions', bid)
    versioned = bool(int(connection.hget('bucket-versions', bid)))
    size = int(float(connection.hget('bucket-sizes', bid)))
    session = get_session(
        json.loads(connection.hget('bucket-accounts', account)))
    s3 = session.client('s3', region_name=region, config=s3config)

    (contents_key,
     contents_method,
     continue_tokens) = BUCKET_OBJ_DESC[versioned]

    with bucket_ops(bid, 'detect'):
        keys = set()
        for delimiter in delimiters:
            method = getattr(s3, contents_method, None)
            results = method(
                Bucket=bucket, Prefix=prefix, Delimiter=delimiter)
            prefixes = [p['Prefix'] for p in results.get('CommonPrefixes', [])]
            contents = results.get(contents_key, [])
            keys.update([k['Key'] for k in contents])
            # If we have common prefixes within limit thresholds go wide
            if (len(prefixes) > 0 and
                len(prefixes) < 1000 and
                    len(contents) < 1000):
                log.info(
                    "%s detected prefix delimiter:%s contents:%d prefixes:%d",
                    bid, delimiter, len(contents), len(prefixes))
                limit = prefix and 2 or 4
                return process_bucket_partitions(
                    bid, partition=delimiter,
                    strategy='p', prefix_set=prefixes, limit=limit)

    # Detect character sets
    charset = get_keys_charset(keys, bid)
    log.info("Detected charset %s for %s", charset, bid)

    # Determine the depth we need to keep total api calls below threshold
    scan_count = size / 1000.0
    for limit in range(1, 4):
        if math.pow(len(charset), limit) * 1000 > scan_count:
            break

    # Dispatch
    prefixes = ('',)
    prefixes = NGramPartition(
        charset, limit=limit).initialize_prefixes(prefixes)

    #
    random.shuffle(prefixes)

    # Pregen on ngram means we have many potentially useless prefixes
    # todo carry charset forward as param, and go incremental on prefix
    # ngram expansion
    connection.hincrby('bucket-partition', bid, len(prefixes))
    return bulk_invoke(
        process_bucket_iterator, [bid], prefixes)
822636
public void ensureCapacity (int minCapacity)
    {
        int size = _buckets.length;
        while (minCapacity > (int) (size * _loadFactor)) {
            size *= 2;
        }
        if (size != _buckets.length) {
            resizeBuckets(size);
        }
    }
1259521
private static boolean bucketHasFastForwardMap(String bucketName, ClusterConfig clusterConfig) {
        if (bucketName == null) {
            return false;
        }
        BucketConfig bucketConfig = clusterConfig.bucketConfig(bucketName);
        return bucketConfig != null && bucketConfig.hasFastForwardMap();
    }
1005775
public static <T> List<List<T>> getBuckets(Collection<Pair<T, Long>> files, double bucketHigh, double bucketLow, long minSSTableSize)
    {
        // Sort the list in order to get deterministic results during the grouping below
        List<Pair<T, Long>> sortedFiles = new ArrayList<Pair<T, Long>>(files);
        Collections.sort(sortedFiles, new Comparator<Pair<T, Long>>()
        {
            public int compare(Pair<T, Long> p1, Pair<T, Long> p2)
            {
                return p1.right.compareTo(p2.right);
            }
        });

        Map<Long, List<T>> buckets = new HashMap<Long, List<T>>();

        outer:
        for (Pair<T, Long> pair: sortedFiles)
        {
            long size = pair.right;

            // look for a bucket containing similar-sized files:
            // group in the same bucket if it's w/in 50% of the average for this bucket,
            // or this file and the bucket are all considered "small" (less than `minSSTableSize`)
            for (Entry<Long, List<T>> entry : buckets.entrySet())
            {
                List<T> bucket = entry.getValue();
                long oldAverageSize = entry.getKey();
                if ((size > (oldAverageSize * bucketLow) && size < (oldAverageSize * bucketHigh))
                    || (size < minSSTableSize && oldAverageSize < minSSTableSize))
                {
                    // remove and re-add under new new average size
                    buckets.remove(oldAverageSize);
                    long totalSize = bucket.size() * oldAverageSize;
                    long newAverageSize = (totalSize + size) / (bucket.size() + 1);
                    bucket.add(pair.left);
                    buckets.put(newAverageSize, bucket);
                    continue outer;
                }
            }

            // no similar bucket found; put it in a new one
            ArrayList<T> bucket = new ArrayList<T>();
            bucket.add(pair.left);
            buckets.put(size, bucket);
        }

        return new ArrayList<List<T>>(buckets.values());
    }
91347
def _recursive_merged_items(self, index):
        
        subdirs = [os.path.join(d, "parts", str(index)) for d in self.localdirs]
        m = ExternalMerger(self.agg, self.memory_limit, self.serializer, subdirs,
                           self.scale * self.partitions, self.partitions, self.batch)
        m.pdata = [{} for _ in range(self.partitions)]
        limit = self._next_limit()

        for j in range(self.spills):
            path = self._get_spill_dir(j)
            p = os.path.join(path, str(index))
            with open(p, 'rb') as f:
                m.mergeCombiners(self.serializer.load_stream(f), 0)

            if get_used_memory() > limit:
                m._spill()
                limit = self._next_limit()

        return m._external_items()
1151372
def _partition(s, sep, find):
    
    idx = find(sep)
    if idx != -1:
        left = s[0:idx]
        return left, sep, s[len(left)+len(sep):]
1265410
private void findAndCacheMinimum(int firstBucket) {
        if (currentMin == null) {
            // find first non-empty bucket
            int currentMinBucket = EMPTY;
            for (int i = firstBucket; i < this.buckets.length; i++) {
                if (buckets[i] != null) {
                    currentMinBucket = i;
                    break;
                }
            }
            // find new minimum and cache it
            if (currentMinBucket >= 0) {
                Node val = buckets[currentMinBucket];
                while (val != null) {
                    if (currentMin == null || compare(val.key, currentMin.key) < 0) {
                        currentMin = val;
                    }
                    val = val.next;
                }
            }
        }
    }
629083
private void expandAndRehash() {
    final int[] newHashSet = new int[hashSet.length * 2];
    final int bucketMask = (newHashSet.length - 1);

    for (int j = 0; j < hashSet.length; j++) {
      final int state = hashSet[j];
      if (state > 0) {
        int slot = hash(state, stateLength(state)) & bucketMask;
        for (int i = 0; newHashSet[slot] > 0;) {
          slot = (slot + (++i)) & bucketMask;
        }
        newHashSet[slot] = state;
      }
    }
    this.hashSet = newHashSet;
  }
496244
private void insertBucketEntryFromSearch(MemorySegment originalBucket, MemorySegment currentBucket,
												int originalBucketOffset, int currentBucketOffset,
												int countInCurrentBucket, long originalForwardPointer,
												int hashCode, long pointer, int partitionNumber) throws IOException {
		boolean checkForResize = false;
		if (countInCurrentBucket < NUM_ENTRIES_PER_BUCKET) {
			// we are good in our current bucket, put the values
			currentBucket.putInt(currentBucketOffset + BUCKET_HEADER_LENGTH + (countInCurrentBucket * HASH_CODE_LEN), hashCode); // hash code
			currentBucket.putLong(currentBucketOffset + BUCKET_POINTER_START_OFFSET + (countInCurrentBucket * POINTER_LEN), pointer); // pointer
			currentBucket.putInt(currentBucketOffset + HEADER_COUNT_OFFSET, countInCurrentBucket + 1); // update count
		}
		else {
			// we go to a new overflow bucket
			final InMemoryPartition<T> partition = this.partitions.get(partitionNumber);
			MemorySegment overflowSeg;
			final int overflowSegmentNum;
			final int overflowBucketOffset;
			
			// first, see if there is space for an overflow bucket remaining in the last overflow segment
			if (partition.nextOverflowBucket == 0) {
				// no space left in last bucket, or no bucket yet, so create an overflow segment
				overflowSeg = getNextBuffer();
				overflowBucketOffset = 0;
				overflowSegmentNum = partition.numOverflowSegments;
				
				// add the new overflow segment
				if (partition.overflowSegments.length <= partition.numOverflowSegments) {
					MemorySegment[] newSegsArray = new MemorySegment[partition.overflowSegments.length * 2];
					System.arraycopy(partition.overflowSegments, 0, newSegsArray, 0, partition.overflowSegments.length);
					partition.overflowSegments = newSegsArray;
				}
				partition.overflowSegments[partition.numOverflowSegments] = overflowSeg;
				partition.numOverflowSegments++;
				checkForResize = true;
			}
			else {
				// there is space in the last overflow segment
				overflowSegmentNum = partition.numOverflowSegments - 1;
				overflowSeg = partition.overflowSegments[overflowSegmentNum];
				overflowBucketOffset = partition.nextOverflowBucket << NUM_INTRA_BUCKET_BITS;
			}
			
			// next overflow bucket is one ahead. if the segment is full, the next will be at the beginning
			// of a new segment
			partition.nextOverflowBucket = (partition.nextOverflowBucket == this.bucketsPerSegmentMask ? 0 : partition.nextOverflowBucket + 1);
			
			// insert the new overflow bucket in the chain of buckets
			
			// 1) set the old forward pointer
			// 2) let the bucket in the main table point to this one
			overflowSeg.putLong(overflowBucketOffset + HEADER_FORWARD_OFFSET, originalForwardPointer);
			final long pointerToNewBucket = (((long) overflowSegmentNum) << 32) | ((long) overflowBucketOffset);
			originalBucket.putLong(originalBucketOffset + HEADER_FORWARD_OFFSET, pointerToNewBucket);
			
			// finally, insert the values into the overflow buckets
			overflowSeg.putInt(overflowBucketOffset + BUCKET_HEADER_LENGTH, hashCode);	// hash code
			overflowSeg.putLong(overflowBucketOffset + BUCKET_POINTER_START_OFFSET, pointer); // pointer
			
			// set the count to one
			overflowSeg.putInt(overflowBucketOffset + HEADER_COUNT_OFFSET, 1);
			if(checkForResize && !this.isResizing) {
				// check if we should resize buckets
				if(this.buckets.length <= getOverflowSegmentCount()) {
					resizeHashTable();
				}
			}
		}
	}
1273776
def exist_partitions(self, prefix_spec=None):
        
        try:
            next(self.partitions.iterate_partitions(spec=prefix_spec))
        except StopIteration:
            return False
        return True
1152903
private void initBuckets() {
        if (buckets != null) {
            return;
        }
        buckets = createBucketList();
        if (inputList == null || inputList.isEmpty()) {
            return;
        }

        // Sort the records by name.
        // Stable sort preserves input order of collation duplicates.
        Collections.sort(inputList, recordComparator);

        // Now, we traverse all of the input, which is now sorted.
        // If the item doesn't go in the current bucket, we find the next bucket that contains it.
        // This makes the process order n*log(n), since we just sort the list and then do a linear process.
        // However, if the user adds an item at a time and then gets the buckets, this isn't efficient, so
        // we need to improve it for that case.

        Iterator<Bucket<V>> bucketIterator = buckets.fullIterator();
        Bucket<V> currentBucket = bucketIterator.next();
        Bucket<V> nextBucket;
        String upperBoundary;
        if (bucketIterator.hasNext()) {
            nextBucket = bucketIterator.next();
            upperBoundary = nextBucket.lowerBoundary;
        } else {
            nextBucket = null;
            upperBoundary = null;
        }
        for (Record<V> r : inputList) {
            // if the current bucket isn't the right one, find the one that is
            // We have a special flag for the last bucket so that we don't look any further
            while (upperBoundary != null &&
                    collatorPrimaryOnly.compare(r.name, upperBoundary) >= 0) {
                currentBucket = nextBucket;
                // now reset the boundary that we compare against
                if (bucketIterator.hasNext()) {
                    nextBucket = bucketIterator.next();
                    upperBoundary = nextBucket.lowerBoundary;
                } else {
                    upperBoundary = null;
                }
            }
            // now put the record into the bucket.
            Bucket<V> bucket = currentBucket;
            if (bucket.displayBucket != null) {
                bucket = bucket.displayBucket;
            }
            if (bucket.records == null) {
                bucket.records = new ArrayList<Record<V>>();
            }
            bucket.records.add(r);
        }
    }
1018247
def check_bucket_exists(self, bucket: str) -> bool:
        
        bucket_obj = self.gcp_client.bucket(bucket)  # type: Bucket
        return bucket_obj.exists()
642271
@Override
	public void clearPartitions() {
		// clear the iterators, so the next call to next() will notice
		this.bucketIterator = null;
		this.probeIterator = null;

		for (int i = this.partitionsBeingBuilt.size() - 1; i >= 0; --i) {
			final BinaryHashPartition p = this.partitionsBeingBuilt.get(i);
			try {
				p.clearAllMemory(this.availableMemory);
			} catch (Exception e) {
				LOG.error("Error during partition cleanup.", e);
			}
		}
		this.partitionsBeingBuilt.clear();

		// clear the partitions that are still to be done (that have files on disk)
		for (final BinaryHashPartition p : this.partitionsPending) {
			p.clearAllMemory(this.availableMemory);
		}
	}
489012
function createBuckets(terms) {
            return _.map(terms, (term) => {
              // 1. see if there are other terms & if they have buckets.
              const retVal = { key: term.key, count: term.doc_count };

              _.each(term, (aggResponse, responseKey) => {
                if (responseKey === 'key' || responseKey === 'doc_count') {
                  return null;
                } else if (aggResponse.buckets) {
                  retVal[responseKey] = createBuckets(aggResponse.buckets);
                } else if (aggResponse.hits && aggResponse.hits.hits) {
                  // top_hits aggs result from nested query w/o reverse nesting.
                  retVal[responseKey] = getTopHitsResult(aggResponse, responseKey, _esResponse, aggregationObjects);
                  // to combine nested aggs w others, you have to un-nest them, & this takes up an aggregation-space.
                } else if (responseKey !== 'reverse_nesting' && aggResponse) { // stats & extended_stats aggs
                  // This means it's the result of a nested stats or extended stats query.
                  if (aggResponse[responseKey]) {
                    retVal[responseKey] = aggResponse[responseKey];
                  } else {
                    retVal[responseKey] = aggResponse;
                  }
                } else if (responseKey === 'reverse_nesting') {
                  _.each(aggResponse, (reverseNestedResponseProperty, reverseNestedResponseKey) => {
                    if (reverseNestedResponseKey === 'doc_count') {
                      return null;
                    } else if (reverseNestedResponseProperty.buckets) {
                      retVal[reverseNestedResponseKey] = createBuckets(reverseNestedResponseProperty.buckets);
                      // this gets a little complicated because reverse-nested then renested subdocuments are ..
                      // complicated (because the extra aggs for nesting throws things off).
                    } else if (reverseNestedResponseProperty[reverseNestedResponseKey] &&
                        reverseNestedResponseProperty[reverseNestedResponseKey].buckets) {
                      retVal[reverseNestedResponseKey] = createBuckets(
                        reverseNestedResponseProperty[reverseNestedResponseKey].buckets);

                      // this gets a little MORE complicated because of reverse-nested then renested top_hits aggs
                    } else if (reverseNestedResponseProperty.hits && reverseNestedResponseProperty.hits.hits) {
                      retVal[reverseNestedResponseKey] = getTopHitsResult(reverseNestedResponseProperty,
                        reverseNestedResponseKey, _esResponse, aggregationObjects);

                      // stats & extended_stats aggs
                    } else if (reverseNestedResponseProperty) {
                      // This means it's the result of a nested stats or extended stats query.
                      if (reverseNestedResponseProperty[reverseNestedResponseKey]) {
                        retVal[reverseNestedResponseKey] = reverseNestedResponseProperty[reverseNestedResponseKey];
                      } else {
                        retVal[reverseNestedResponseKey] = reverseNestedResponseProperty;
                      }
                    }
                    return null;
                  });
                }
                return null;
              });

              return retVal;
            });
          }
1195024
private void prefetch(long storageIndex) {
        long startIndex = storageIndex / BYTES_IN_DATA;
        // Inc to next bucket
        startIndex += 128;

        if (mPrefetchedBuckets.contains(startIndex)) {
            mPrefetchedBuckets.remove(startIndex);
            return;
        }

        for (int i = 0; i < BUCKETS_TO_PREFETCH; i++) {
            if ((startIndex + i) > (mNodeNumbers / 128)) {
                return;
            }

            mRtx.moveTo(startIndex);
            startIndex += 128;
        }
    }
1179571
@SuppressWarnings("unchecked")
  private Iterator<String> findConfigRefs(@NotNull final Resource startResource, @NotNull final Collection<String> bucketNames) {

    // collect all context path resources (but filter out those without config reference)
    final Iterator<ContextResource> contextResources = new FilterIterator(contextPathStrategy.findContextResources(startResource),
        new Predicate() {
          @Override
          public boolean evaluate(Object object) {
            ContextResource contextResource = (ContextResource)object;
            return StringUtils.isNotBlank(contextResource.getConfigRef());
          }
        });

    // get config resource path for each context resource, filter out items where not reference could be resolved
    final Iterator<String> configPaths = new TransformIterator(contextResources, new Transformer() {
      @Override
      public Object transform(Object input) {
        final ContextResource contextResource = (ContextResource)input;
        String val = checkPath(contextResource, contextResource.getConfigRef(), bucketNames);
        if (val != null) {
          log.trace("+ Found reference for context path {}: {}", contextResource.getResource().getPath(), val);
        }
        return val;
      }
    });
    return new FilterIterator(configPaths, PredicateUtils.notNullPredicate());
  }
716936
private boolean resizeHashTable() throws IOException {
		final int newNumBuckets = 2*this.numBuckets;
		final int bucketsPerSegment = this.bucketsPerSegmentMask + 1;
		final int newNumSegments = (newNumBuckets + (bucketsPerSegment-1)) / bucketsPerSegment;
		final int additionalSegments = newNumSegments-this.buckets.length;
		final int numPartitions = this.partitions.size();
		
		if (this.availableMemory.size() < additionalSegments) {
			for (int i = 0; i < numPartitions; i++) {
				compactPartition(i);
				if(this.availableMemory.size() >= additionalSegments) {
					break;
				}
			}
		}
		
		if (this.availableMemory.size() < additionalSegments || this.closed) {
			return false;
		}
		else {
			this.isResizing = true;
			// allocate new buckets
			final int startOffset = (this.numBuckets * HASH_BUCKET_SIZE) % this.segmentSize;
			final int oldNumBuckets = this.numBuckets;
			final int oldNumSegments = this.buckets.length;
			MemorySegment[] mergedBuckets = new MemorySegment[newNumSegments];
			System.arraycopy(this.buckets, 0, mergedBuckets, 0, this.buckets.length);
			this.buckets = mergedBuckets;
			this.numBuckets = newNumBuckets;
			// initialize all new buckets
			boolean oldSegment = (startOffset != 0);
			final int startSegment = oldSegment ? (oldNumSegments-1) : oldNumSegments;
			for (int i = startSegment, bucket = oldNumBuckets; i < newNumSegments && bucket < this.numBuckets; i++) {
				MemorySegment seg;
				int bucketOffset;
				if(oldSegment) { // the first couple of new buckets may be located on an old segment
					seg = this.buckets[i];
					for (int k = (oldNumBuckets % bucketsPerSegment) ; k < bucketsPerSegment && bucket < this.numBuckets; k++, bucket++) {
						bucketOffset = k * HASH_BUCKET_SIZE;	
						// initialize the header fields
						seg.put(bucketOffset + HEADER_PARTITION_OFFSET, assignPartition(bucket, (byte)numPartitions));
						seg.putInt(bucketOffset + HEADER_COUNT_OFFSET, 0);
						seg.putLong(bucketOffset + HEADER_FORWARD_OFFSET, BUCKET_FORWARD_POINTER_NOT_SET);
					}
				} else {
					seg = getNextBuffer();
					// go over all buckets in the segment
					for (int k = 0; k < bucketsPerSegment && bucket < this.numBuckets; k++, bucket++) {
						bucketOffset = k * HASH_BUCKET_SIZE;
						// initialize the header fields
						seg.put(bucketOffset + HEADER_PARTITION_OFFSET, assignPartition(bucket, (byte)numPartitions));
						seg.putInt(bucketOffset + HEADER_COUNT_OFFSET, 0);
						seg.putLong(bucketOffset + HEADER_FORWARD_OFFSET, BUCKET_FORWARD_POINTER_NOT_SET);
					}
				}				
				this.buckets[i] = seg;
				oldSegment = false; // we write on at most one old segment
			}
			int hashOffset;
			int hash;
			int pointerOffset;
			long pointer;
			IntArrayList hashList = new IntArrayList(NUM_ENTRIES_PER_BUCKET);
			LongArrayList pointerList = new LongArrayList(NUM_ENTRIES_PER_BUCKET);
			IntArrayList overflowHashes = new IntArrayList(64);
			LongArrayList overflowPointers = new LongArrayList(64);
			
			// go over all buckets and split them between old and new buckets
			for (int i = 0; i < numPartitions; i++) {
				InMemoryPartition<T> partition = this.partitions.get(i);
				final MemorySegment[] overflowSegments = partition.overflowSegments;
				
				int posHashCode;
				for (int j = 0, bucket = i; j < this.buckets.length && bucket < oldNumBuckets; j++) {
					MemorySegment segment = this.buckets[j];
					// go over all buckets in the segment belonging to the partition
					for (int k = bucket % bucketsPerSegment; k < bucketsPerSegment && bucket < oldNumBuckets; k += numPartitions, bucket += numPartitions) {
						int bucketOffset = k * HASH_BUCKET_SIZE;
						if((int)segment.get(bucketOffset + HEADER_PARTITION_OFFSET) != i) {
							throw new IOException("Accessed wrong bucket! wanted: " + i + " got: " + segment.get(bucketOffset + HEADER_PARTITION_OFFSET));
						}
						// loop over all segments that are involved in the bucket (original bucket plus overflow buckets)
						int countInSegment = segment.getInt(bucketOffset + HEADER_COUNT_OFFSET);
						int numInSegment = 0;
						pointerOffset = bucketOffset + BUCKET_POINTER_START_OFFSET;
						hashOffset = bucketOffset + BUCKET_HEADER_LENGTH;
						while (true) {
							while (numInSegment < countInSegment) {
								hash = segment.getInt(hashOffset);
								if((hash % this.numBuckets) != bucket && (hash % this.numBuckets) != (bucket+oldNumBuckets)) {
									throw new IOException("wanted: " + bucket + " or " + (bucket + oldNumBuckets) + " got: " + hash%this.numBuckets);
								}
								pointer = segment.getLong(pointerOffset);
								hashList.add(hash);
								pointerList.add(pointer);
								pointerOffset += POINTER_LEN;
								hashOffset += HASH_CODE_LEN;
								numInSegment++;
							}
							// this segment is done. check if there is another chained bucket
							final long forwardPointer = segment.getLong(bucketOffset + HEADER_FORWARD_OFFSET);
							if (forwardPointer == BUCKET_FORWARD_POINTER_NOT_SET) {
								break;
							}
							final int overflowSegNum = (int) (forwardPointer >>> 32);
							segment = overflowSegments[overflowSegNum];
							bucketOffset = (int) forwardPointer;
							countInSegment = segment.getInt(bucketOffset + HEADER_COUNT_OFFSET);
							pointerOffset = bucketOffset + BUCKET_POINTER_START_OFFSET;
							hashOffset = bucketOffset + BUCKET_HEADER_LENGTH;
							numInSegment = 0;
						}
						segment = this.buckets[j];
						bucketOffset = k * HASH_BUCKET_SIZE;
						// reset bucket for re-insertion
						segment.putInt(bucketOffset + HEADER_COUNT_OFFSET, 0);
						segment.putLong(bucketOffset + HEADER_FORWARD_OFFSET, BUCKET_FORWARD_POINTER_NOT_SET);
						// refill table
						if(hashList.size() != pointerList.size()) {
							throw new IOException("Pointer and hash counts do not match. hashes: " + hashList.size() + " pointer: " + pointerList.size());
						}
						int newSegmentIndex = (bucket + oldNumBuckets) / bucketsPerSegment;
						MemorySegment newSegment = this.buckets[newSegmentIndex];
						
						// we need to avoid overflows in the first run
						int oldBucketCount = 0;
						int newBucketCount = 0;
						while (!hashList.isEmpty()) {
							hash = hashList.removeLast();
							pointer = pointerList.removeLong(pointerList.size()-1);
							posHashCode = hash % this.numBuckets;
							if (posHashCode == bucket && oldBucketCount < NUM_ENTRIES_PER_BUCKET) {
								bucketOffset = (bucket % bucketsPerSegment) * HASH_BUCKET_SIZE;
								insertBucketEntryFromStart(segment, bucketOffset, hash, pointer, partition.getPartitionNumber());
								oldBucketCount++;
							}
							else if (posHashCode == (bucket + oldNumBuckets) && newBucketCount < NUM_ENTRIES_PER_BUCKET) {
								bucketOffset = ((bucket + oldNumBuckets) % bucketsPerSegment) * HASH_BUCKET_SIZE;
								insertBucketEntryFromStart(newSegment, bucketOffset, hash, pointer, partition.getPartitionNumber());
								newBucketCount++;
							}
							else if (posHashCode == (bucket + oldNumBuckets) || posHashCode == bucket) {
								overflowHashes.add(hash);
								overflowPointers.add(pointer);
							}
							else {
								throw new IOException("Accessed wrong bucket. Target: " + bucket + " or " + (bucket + oldNumBuckets) + " Hit: " + posHashCode);
							}
						}
						hashList.clear();
						pointerList.clear();
					}
				}
				// reset partition's overflow buckets and reclaim their memory
				this.availableMemory.addAll(partition.resetOverflowBuckets());
				// clear overflow lists
				int bucketArrayPos;
				int bucketInSegmentPos;
				MemorySegment bucket;
				while(!overflowHashes.isEmpty()) {
					hash = overflowHashes.removeLast();
					pointer = overflowPointers.removeLong(overflowPointers.size()-1);
					posHashCode = hash % this.numBuckets; 
					bucketArrayPos = posHashCode >>> this.bucketsPerSegmentBits;
					bucketInSegmentPos = (posHashCode & this.bucketsPerSegmentMask) << NUM_INTRA_BUCKET_BITS;
					bucket = this.buckets[bucketArrayPos];
					insertBucketEntryFromStart(bucket, bucketInSegmentPos, hash, pointer, partition.getPartitionNumber());
				}
				overflowHashes.clear();
				overflowPointers.clear();
			}
			this.isResizing = false;
			return true;
		}
	}