CurrentHashMap巧妙利用位運算獲取數組指定下標元素

先來了解一下數組對象在堆中的存儲形式【數組長度，數組元素類型信息等】+ 【存放元素對象的空間】

基礎信息	實例數據		內存填充
Mark Word,ClassPointer,數組長度	第一個元素	第二個元素	固定的填充內容

所以我們想要獲取某個下標的元素首先要獲取這個元素的起始位置和每個元素長度

例如我們要取第二個元素的，首先知道第二個元素的起始位置，從其實位置開始按照每個元素的長度取指定的位數，就相當于獲取了第二個元素的全部信息。

再來了解一下Java中一個特殊的類sun.misc.Unsafe

sun.misc.Unsafe是JDK提供的用于很底層編程的類，位于sun.misc包中。在有些底層編程的場景，Java語言層面辦不到的事情，我們可能需要使用JNI，借助C語言去實現。但是使用JNI并不是唯一的選擇，使用JNI會將代碼綁定到特定的平臺，使用Unsafe類可以保留Java語言代碼對平臺的獨立性，又實現底層編程。

Unsafe類并沒有public的構造函數，只提供了一個靜態工廠方法，這個靜態方法還只提供給JDK標準庫自身的類調用，在我們自己隨便建的一個普通的類調用這個靜態工廠方法還會拋異常。

這個靜態工廠方法的代碼如下：

@CallerSensitive
public static Unsafe getUnsafe() {Class<?> caller = Reflection.getCallerClass();if (!VM.isSystemDomainLoader(caller.getClassLoader()))throw new SecurityException("Unsafe");return theUnsafe;
}

可以使用反射的方式

import sun.misc.Unsafe;
import java.lang.reflect.Field;public class TestUnsafe {private static Unsafe unsafe;static {try {Field f = Unsafe.class.getDeclaredField("theUnsafe");f.setAccessible(true);unsafe = (Unsafe) f.get(null);} catch (Exception e) {//}}}

?Unsafe功能列表

allocateMemory/freeMemory，分配、釋放堆外內存DirectMemory（和c/cpp中的malloc一樣）
CAS操作
copyMemory
defineClass(without security checks)
get/put address 使用堆外內存地址進行數據的讀寫操作
get/put volatile 使用堆外內存地址進行數據的讀寫操作 - volatile版本
loadFence/storeFence/fullFence 禁止指令重排序
park/unpark 阻塞/解除阻塞線程

Unsafe的數組操作

unsafe中，有兩個關于數組的方法：

public native int arrayBaseOffset(Class<?> arrayClass);
public native int arrayIndexScale(Class<?> arrayClass);

arrayBaseOffset 數組第一個元素相對于數組對象起始地址的偏移量

arrayIndexScale就是指數組中每個元素所占用的空間大小，比如int[] scale就是4，long[] scale就是8，object[] scale就是4（指針大小）

// Unsafe mechanicsprivate static final sun.misc.Unsafe U;private static final long SIZECTL;private static final long TRANSFERINDEX;private static final long BASECOUNT;private static final long CELLSBUSY;private static final long CELLVALUE;private static final long ABASE;private static final int ASHIFT;static {try {U = sun.misc.Unsafe.getUnsafe();Class<?> k = ConcurrentHashMap.class;SIZECTL = U.objectFieldOffset(k.getDeclaredField("sizeCtl"));TRANSFERINDEX = U.objectFieldOffset(k.getDeclaredField("transferIndex"));BASECOUNT = U.objectFieldOffset(k.getDeclaredField("baseCount"));CELLSBUSY = U.objectFieldOffset(k.getDeclaredField("cellsBusy"));Class<?> ck = CounterCell.class;CELLVALUE = U.objectFieldOffset(ck.getDeclaredField("value"));Class<?> ak = Node[].class;ABASE = U.arrayBaseOffset(ak);int scale = U.arrayIndexScale(ak);if ((scale & (scale - 1)) != 0)throw new Error("data type scale not a power of two");ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);} catch (Exception e) {throw new Error(e);}}

這是CurrentHashMap中的源碼我們需要注意的地方有：

Class<?> ak = Node[].class; 
ABASE = U.arrayBaseOffset(ak);

ABASE:數組第一個元素相對于數組對象起始地址的偏移量
int scale = U.arrayIndexScale(ak);數組中每個元素所占用的空間大小，返回的是所占空間的字節數
scale為2的n次方,2的n次方二進制表示就是某個位置為1其余位置為0
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
Integer.numberOfLeadingZeros(scale) 計算int型參數二進制表示數值最高位前面有幾個0
由于int一共有32位,出去位1的一位剩下31位，31 - Integer.numberOfLeadingZeros(scale)就表示scale二進制表示最低位有幾個連續的0

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 32
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 32位
000000000000000000000000000(27位)	1	00000(5位)
Integer.numberOfLeadingZeros()		31 - Integer.numberOfLeadingZeros()

    @Testpublic void printObjectArrayScale() throws NoSuchFieldException, IllegalAccessException {Field theUnsafeInstance = Unsafe.class.getDeclaredField("theUnsafe");theUnsafeInstance.setAccessible(true);Unsafe U = (Unsafe) theUnsafeInstance.get(Unsafe.class);Class<?> objectArr = Object[].class;Class<?> intArr = int[].class;Class<?> longArr = long[].class;Class<?> byteArr = byte[].class;int objectScale = U.arrayIndexScale(objectArr);int intScale = U.arrayIndexScale(intArr);int longScale = U.arrayIndexScale(longArr);int byteScale = U.arrayIndexScale(byteArr);System.out.println("Object[]的sacle=" + objectScale);System.out.println("int[]的sacle=" + intScale);System.out.println("long[]的sacle=" + longScale);System.out.println("byte[]的sacle=" + byteScale);
}

可以通過上面的方法測試，引用類型的數組的scale是4，因為雖然不同對象占用內存大小不一，但是對象數組每個元素是指向對應對象的引用，即內存地址

常規的想法是通過 scale * index 來計算某個元素相對于起始位置的偏移量

    @Testpublic void findArrayByBaseAndScale() throws NoSuchFieldException, IllegalAccessException {Class<Unsafe> clazz = Unsafe.class;Field unsafeField = clazz.getDeclaredField("theUnsafe");unsafeField.setAccessible(true);Unsafe unsafe = (Unsafe)unsafeField.get(null);int[] temp = {1, 2, 3 , 4};int base = unsafe.arrayBaseOffset(int[].class);int scale = unsafe.arrayIndexScale(int[].class);System.out.println(unsafe.getInt(temp , base + 0 * scale));System.out.println(unsafe.getInt(temp , base + 1 * scale));System.out.println(unsafe.getInt(temp , base + 2 * scale));System.out.println(unsafe.getInt(temp , base + 3 * scale));
}

?可以看到順利取到了數組元素

這里看看CurrentHashMap是怎么計算元素的偏移量的

    @SuppressWarnings("unchecked")static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);}

這里測試一下它的這種方法

    @Testpublic void findArrayByBaseAndScale1() throws NoSuchFieldException, IllegalAccessException {Class<Unsafe> clazz = Unsafe.class;Field unsafeField = clazz.getDeclaredField("theUnsafe");unsafeField.setAccessible(true);Unsafe unsafe = (Unsafe)unsafeField.get(null);int[] temp = {1, 2, 3 , 4};int base = unsafe.arrayBaseOffset(int[].class);int scale = unsafe.arrayIndexScale(int[].class);int ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);System.out.println("第一個元素:" + unsafe.getInt(temp , base + (0 << ASHIFT) ));System.out.println("第二個元素:" + unsafe.getInt(temp , base + (1 << ASHIFT) ));System.out.println("第三個元素:" + unsafe.getInt(temp , base + (2 << ASHIFT) ));System.out.println("第四個元素:" + unsafe.getInt(temp , base + (3 << ASHIFT) ));}

?可以看到也順利取到了數組的元素

熟悉位運算的很容易理解，其實這就是利用了一個位運算的技巧，通過向左移來實現擴大為2的n次方倍，而scale正好是2的n次方，所以可以這樣計算

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/42623.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/42623.shtml
英文地址，請注明出處：http://en.pswp.cn/web/42623.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！