竞技宝app下载:PHP内核探索之变量(3)- hash table

2020-02-07 10:45栏目:竞技宝app
TAG:

在游戏后台中,内存的数据查找是一个很重要,也是关系到我们游戏的后台效率的问题。在大量的数据中,我们如何让我们的的程序能够快速的查找到我们所想要的数据呢。那么我们就要使用相应的算法了。首先,我们所有使用的内存都是通过分配内存的方式,基本上都是共享内存。通过shmid来分配内存。那么游戏中有哪些数据呢。1.配置表数据,这个数据是程序启动的时候,就要加载到内存中,我们就使用了二分法,将这些数据放到相应的二维数组中,这些内存都是使用二分法进行有序排列。在查找的时候,其效率是logN,也就是基本符合了我们的要求。2.运行时数据,这个就要使用了各种方法来加速我们的快速查找了。当一个心的用户登录到我们的服务器,我们会现在内存池中进行内存的分配工作,然后记录玩家内存池的索引,和内存ID然后,我们在讲根据内存的数组索引,进行对玩家的名字还有内存id等进行hash存储。因此,当我们要查找一个玩家的时候,我们先通过其hash查找,然后得到其内存池索引,直接通过数组下标,取得玩家的数据,效率非常的高效。3.地图数据。地图数据分配在内存池等等,我们还是用了nginx页内存的分配策略。加速了内存的的使用。因此,根据不同的情况,达到我们高效率的内存数据查找,是至关重要的。

       在PHP中,除了zval, 另一个比较重要的数据结构非hash table莫属,例如我们最常见的数组,在底层便是hash table。除了数组,在线程安全(TSRM)、GC、资源管理、Global变量、ini配置管理中,几乎都有Hash table的踪迹(上一次我们也提到,符号表也是使用Hash table实现的)。那么,在PHP中,这种数据有什么特殊之处,结构是怎么实现的? 带着这些问题,我们开始本次的内核探索之旅。

ArrayMap的工作原理(Android 7.1源码)

其他相关文章

  1. 源码的魅力 - ArrayDeque 的工作原理
  2. 源码的魅力 - HashMap 的工作原理
  3. 源码的魅力 - TreeMap 的工作原理
  4. GankIo又一个ReactNative客户端

简介

鉴于HashMap的内存使用率太低,而内存又是Android设备系统中极其宝贵的资源,所以Google开发出ArrayMap来一定条件下取代HashMap (几乎平时的开发都可以使用这个结构,而不用HashMap)。

初始化

    int[] mHashes;
    Object[] mArray;

   public ArrayMap(int capacity, boolean identityHashCode) {
       mIdentityHashCode = identityHashCode;

       if (capacity < 0) {
           mHashes = EMPTY_IMMUTABLE_INTS;
           mArray = EmptyArray.OBJECT;
       } else if (capacity == 0) {
           mHashes = EmptyArray.INT;
           mArray = EmptyArray.OBJECT;
       } else {
           allocArrays(capacity);
       }
       mSize = 0;
   }

ArrayMap的内部主要依靠mHashes以及mArray,构造函数中可以看出和HashMap一样一上来创建时并不会分配内存空间。此处的mhashes就是存放HashCode的数组,mArray时存放key与Value的数组。

put 方法

    @Override
    public V put(K key, V value) {
        final int hash;
        int index;
        if (key == null) {
            hash = 0;
            index = indexOfNull();
        } else {
            hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
            index = indexOf(key, hash);
        }
        if (index >= 0) {
            index = (index<<1) + 1;
            final V old = (V)mArray[index];
            mArray[index] = value;
            return old;
        }

        index = ~index;
        if (mSize >= mHashes.length) {
            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

            if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            allocArrays(n);

            if (mHashes.length > 0) {
                if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }

            freeArrays(ohashes, oarray, mSize);
        }

        if (index < mSize) {
            if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
                    + " to " + (index+1));
            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
        }

        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;
        return null;
    }
  • 当key为空时直接通过indexOfNull获取
    index
  • 当key不为空时,hash = key.hashCode获取hash值,并且通过indexOf方法来获取位置(indexOf与indexOfNull将在下面详细分析)
  • 如果返回的index大于零,直接通过index = (index << 1)+ 1来获取到mArray数组的索引直接替换数据(由于mArray存放的数据是一个key然后一个Value形式的, index* 2就是key的位置,再加一就是value的位置)
  • 当没有找到key的位置时,返回的index是负数,通过取反来获取到新插入的位置。
  • 当mHash列表满了的时候,执行扩容方法allocArrays() allocArrays与下面的freeArrays方法将在后面进行分析
  • 将老数据分配到分配到新数组中。
  • 由于此时需要在index位置新插入数据,所以需要将mHashcodes以及mArray中的数据向右移动,在mHashcodes数组中腾出一个位置,mArray中腾出两个位置。
  • 将新数据插入,mSize自增

竞技宝app下载 1

结构图

indexOf以及indexOfNull方法

由于indexOfNull其实就是hash参数为0的特殊版本,基本上是一样的所以就不赘述了。

  //获取索引值
  int indexOf(Object key, int hash) {
      final int N = mSize;

      // Important fast case: if nothing is in here, nothing to look for.
      if (N == 0) {
          return ~0;
      }

      int index = ContainerHelpers.binarySearch(mHashes, N, hash);

      // If the hash code wasn't found, then we have no entry for this key.
      if (index < 0) {
          return index;
      }

      // If the key at the returned index matches, that's what we want.
      if (key.equals(mArray[index<<1])) {
          return index;
      }

      // Search for a matching key after the index.
      int end;
      for (end = index + 1; end < N && mHashes[end] == hash; end++) {
          if (key.equals(mArray[end << 1])) return end;
      }

      // Search for a matching key before the index.
      for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
          if (key.equals(mArray[i << 1])) return i;
      }

      // Key not found -- return negative value indicating where a
      // new entry for this key should go.  We use the end of the
      // hash chain to reduce the number of array entries that will
      // need to be copied when inserting.
      return ~end;
  }

  static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }
  • 当之前没有数据时,则返回0的取反值。
  • 通过二分法在ContainerHelpers.binarySearch()中查找数据
  • 在binarySearch函数当数值并没有的时候,会返回lo的取反值,这个lo此时指向的位置是Value插入的位置。(其实这个取反以及其他位置的取反就是整个ArrayMap中巧妙的地方之一,binarySearch通过返回取反值既做到了数据不存在时返回负数,又提供了数据新插入的位置,一举多得。
  • 当返回的index为负数时,直接返回索引值。
  • 如果key正好是在mArray的2*index的位置的数据,则直接返回index
  • 如果还是不对,则通过mHashs向下查找,如果存在相同的hash值,并且对应的key也相等则返回index值。
  • 反之则向下查找。
  • 如果还是没有找到,直接返回end(end 是 等于index + 1)的值取反值

总结:indexOf函数返回正数时是存在key值的mHashCodes数组的索引值,否则返回负值就是在mHashCode新插入位置的索引的取反值,再取反就可以得到插入的位置

allocArrays以及freeArrays函数

    private void allocArrays(final int size) {
        if (mHashes == EMPTY_IMMUTABLE_INTS) {
            throw new UnsupportedOperationException("ArrayMap is immutable");
        }
        if (size == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCache != null) {
                    final Object[] array = mTwiceBaseCache;
                    mArray = array;
                    mTwiceBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mTwiceBaseCacheSize--;
                    if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
                            + " now have " + mTwiceBaseCacheSize + " entries");
                    return;
                }
            }
        } else if (size == BASE_SIZE) {
            synchronized (ArrayMap.class) {
                if (mBaseCache != null) {
                    final Object[] array = mBaseCache;
                    mArray = array;
                    mBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mBaseCacheSize--;
                    if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
                            + " now have " + mBaseCacheSize + " entries");
                    return;
                }
            }
        }

        mHashes = new int[size];
        mArray = new Object[size<<1];
    }

    private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
        if (hashes.length == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCacheSize < CACHE_SIZE) {
                    array[0] = mTwiceBaseCache;
                    array[1] = hashes;
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    mTwiceBaseCache = array;
                    mTwiceBaseCacheSize++;
                    if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
                            + " now have " + mTwiceBaseCacheSize + " entries");
                }
            }
        } else if (hashes.length == BASE_SIZE) {
            synchronized (ArrayMap.class) {
                if (mBaseCacheSize < CACHE_SIZE) {
                    array[0] = mBaseCache;
                    array[1] = hashes;
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    mBaseCache = array;
                    mBaseCacheSize++;
                    if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
                            + " now have " + mBaseCacheSize + " entries");
                }
            }
        }
    }

ArrayMap通过两个数组mTwiceBaseCache以及mBaseCache两个数组来提供缓存内存空间,但只有在数组大小是4与8时发挥作用。

final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
       : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

前面的put中扩展数组部分代码中,当小于4时扩展成4,小于8时扩展成8,否则增加一半的 mSize大小。
allocArrays与freeArrays在缓存部分是相对应的,作用是将原先的那部分内存空间保存住,不然垃圾回收器回收掉。

总结

ArrayMap在内存使用率上比HashMap高不少,但是插入速度在数据很多时会很慢,所以ArrayMap在数据量少时(千以内)比较适用,否则还是要使用HashMap。


更多好文章请关注微信公众号【Android技术栈】,微信公众号刚刚创建不久希望大家多多支持。

竞技宝app下载 2

Android技术栈

      本文主要内容:

  1. Hash table的基本介绍
  2. PHP底层Hash table的结构和实现
  3. Zend Hash table API

版权声明:本文由龙竞技官网发布于竞技宝app,转载请注明出处:竞技宝app下载:PHP内核探索之变量(3)- hash table